✏️
leetcode solution
  • Leetcode Solutions
  • LeetCode 1. Two Sum
  • LeetCode 2. Add Two Numbers
  • LeetCode 3. Longest Substring Without Repeating Characters
  • LeetCode 4. Median of Two Sorted Arrays
  • LeetCode 5. Longest Palindromic Substring
  • LeetCode 6. ZigZag Conversion
  • LeetCode 7. Reverse Integer
  • LeetCode 8. String to Integer (atoi)
  • LeetCode 9. Palindrome Number
  • LeetCode 10. Regular Expression Matching
  • LeetCode 11. Container With Most Water
  • LeetCode 12. Integer to Roman
  • LeetCode 13. Roman to Integer
  • LeetCode 14. Longest Common Prefix
  • LeetCode 15. 3Sum
  • LeetCode 16. 3Sum Closest
  • LeetCode 17. Letter Combinations of a Phone Number
  • LeetCode 18. 4Sum
  • LeetCode 19. Remove Nth Node From End of List
  • LeetCode 20. Valid Parentheses
  • LeetCode 21. Merge Two Sorted Lists
  • LeetCode 22. Generate Parentheses
  • LeetCode 23. Merge k Sorted Lists
  • LeetCode 24. Swap Nodes in Pairs
  • LeetCode 25. Reverse Nodes in k-Group
  • LeetCode 26. Remove Duplicates from Sorted Array
  • LeetCode 27. Remove Element
  • LeetCode 28. Implement strStr()
  • LeetCode 29. Divide Two Integers
  • LeetCode 30. Substring with Concatenation of All Words
  • LeetCode 31. Next Permutation
  • LeetCode 32. Longest Valid Parentheses
  • LeetCode 33. Search in Rotated Sorted Array
  • LeetCode 42. Trapping Rain Water
  • LeetCode 56. Merge Intervals
  • LeetCode 67. Add Binary
  • LeetCode 81. Search in Rotated Sorted Array II
  • LeetCode 124. Binary Tree Maximum Path Sum
  • LeetCode 125. Valid Palindrome
  • LeetCode 153. Find Minimum in Rotated Sorted Array
  • LeetCode 154. Find Minimum in Rotated Sorted Array II
  • LeetCode 157. Read N Characters Given Read4
  • LeetCode 158. Read N Characters Given Read4 II - Call multiple times
  • LeetCode 236. Lowest Common Ancestor of a Binary Tree
  • LeetCode 238. Product of Array Except Self
  • LeetCode 269. Alien Dictionary
  • Leetcode 295. Find Median from Data Stream
  • Leetcode 297. Serialize and Deserialize Binary Tree
  • LeetCode 300. Longest Increasing Subsequence
  • LeetCode 301. Remove Invalid Parentheses
  • LeetCode 336. Palindrome Pairs
  • LeetCode 407. Trapping Rain Water II
  • LeetCode 415. Add Strings
  • LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List
  • LeetCode 489. Robot Room Cleaner
  • LeetCode 560. Subarray Sum Equals K
  • LeetCode 680. Valid Palindrome II
  • LeetCode 710. Random Pick with Blacklist
  • LeetCode 721. Accounts Merge
  • LeetCode 863. All Nodes Distance K in Binary Tree
  • LeetCode 918. Maximum Sum Circular Subarray
  • LeetCode 953. Verifying an Alien Dictionary
  • LeetCode 973. K Closest Points to Origin
  • LeetCode 1249. Minimum Remove to Make Valid Parentheses
  • LeetCode 1428. Leftmost Column with at Least a One
  • LeetCode 1570. Dot Product of Two Sparse Vectors
  • LeetCode 1644. Lowest Common Ancestor of a Binary Tree II
  • LeetCode 1650. Lowest Common Ancestor of a Binary Tree III
  • LeetCode 1676. Lowest Common Ancestor of a Binary Tree IV
  • Leetcode 1727. Largest Submatrix With Rearrangements
  • LeetCode 1751. Maximum Number of Events That Can Be Attended II
  • LeetCode 1754. Largest Merge Of Two Strings
  • LeetCode 1755. Closest Subsequence Sum
  • LeetCode 1760. Minimum Limit of Balls in a Bag
  • LeetCode 1761. Minimum Degree of a Connected Trio in a Graph
  • LeetCode 1764. Form Array by Concatenating Subarrays of Another Array
  • LeetCode 1765. Map of Highest Peak
  • LeetCode 1766. Tree of Coprimes
  • LeetCode 1770. Maximum Score from Performing Multiplication Operations
  • LeetCode 1771. Maximize Palindrome Length From Subsequences
  • LeetCode 1774. Closest Dessert Cost
  • LeetCode. 1775 Equal Sum Arrays With Minimum Number of Operations
  • LeetCode 1776. Car Fleet II
  • LeetCode 1778. Shortest Path in a Hidden Grid
  • LeetCode 1779. Find Nearest Point That Has the Same X or Y Coordinate
  • LeetCode 1780. Check if Number is a Sum of Powers of Three
  • LeetCode 1781. Sum of Beauty of All Substrings
  • LeetCode 1782. Count Pairs Of Nodes
  • LeetCode 1784. Check if Binary String Has at Most One Segment of Ones
  • LeetCode 1785. Minimum Elements to Add to Form a Given Sum
  • LeetCode 1786. Number of Restricted Paths From First to Last Node
  • LeetCode 1787. Make the XOR of All Segments Equal to Zero
  • LeetCode 1788. Maximize the Beauty of the Garden
  • LeetCode 1790. Check if One String Swap Can Make Strings Equal
  • LeetCode 1791. Find Center of Star Graph
  • LeetCode 1792. Maximum Average Pass Ratio
  • LeetCode 1793. Maximum Score of a Good Subarray
  • LeetCode 1794. Count Pairs of Equal Substrings With Minimum Difference
  • LeetCode 1796. Second Largest Digit in a String
  • LeetCode 1797. Design Authentication Manager
  • LeetCode 1798. Maximum Number of Consecutive Values You Can Make
  • LeetCode 1799. Maximize Score After N Operations
  • LeetCode 1800. Maximum Ascending Subarray Sum
  • LeetCode 1801. Number of Orders in the Backlog
  • LeetCode 1802. Maximum Value at a Given Index in a Bounded Array
  • LeetCode 1803. Count Pairs With XOR in a Range
  • LeetCode 1804. Implement Trie II (Prefix Tree)
  • LeetCode 1805. Number of Different Integers in a String
  • LeetCode 1807. Evaluate the Bracket Pairs of a String
  • LeetCode 1808. Maximize Number of Nice Divisors
  • LeetCode 1810. Minimum Path Cost in a Hidden Grid
  • LeetCode 1812. Determine Color of a Chessboard Square
  • LeetCode 1813. Sentence Similarity III
  • LeetCode 1814. Count Nice Pairs in an Array
  • LeetCode 1815. Maximum Number of Groups Getting Fresh Donuts
  • LeetCode 1816. Truncate Sentence
  • LeetCode 1817. Finding the Users Active Minutes
  • LeetCode 1818. Minimum Absolute Sum Difference
  • LeetCode 1819. Number of Different Subsequences GCDs
  • LeetCode 1820. Maximum Number of Accepted Invitations
  • LeetCode 1822. Sign of the Product of an Array
  • LeetCode 1824. Minimum Sideway Jumps
  • LeetCode 1825. Finding MK Average
  • LeetCode 1826. Faulty Sensor
  • LeetCode 1827. Minimum Operations to Make the Array Increasing
  • LeetCode 1828. Queries on Number of Points Inside a Circle
  • LeetCode 1829. Maximum XOR for Each Query
  • LeetCode 1830. Minimum Number of Operations to Make String Sorted
  • LeetCode 1832. Check if the Sentence Is Pangram
  • LeetCode 1833. Maximum Ice Cream Bars
  • LeetCode 1834. Single-Threaded CPU
  • LeetCode 1835. Find XOR Sum of All Pairs Bitwise AND
  • LeetCode 1836. Remove Duplicates From an Unsorted Linked List
  • LeetCode 1837. Sum of Digits in Base K
  • LeetCode 1839. Longest Substring Of All Vowels in Order
  • LeetCode 1840. Maximum Building Height
  • LeetCode 1847. Closest Room
  • LeetCode 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number
  • LeetCode 1851. Minimum Interval to Include Each Query
Powered by GitBook
On this page

Was this helpful?

LeetCode 973. K Closest Points to Origin

PreviousLeetCode 953. Verifying an Alien DictionaryNextLeetCode 1249. Minimum Remove to Make Valid Parentheses

Last updated 4 years ago

Was this helpful?

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e, √(x1 - x2)2 + (y1 - y2)2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Example 1:

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.

Constraints:

  • 1 <= k <= points.length <= 104

  • -104 < xi, yi < 104

Solution:

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        auto cmp = [&](const vector<int>& a, const vector<int>& b) {
            return a[0] * a[0] + a[1] * a[1] <  b[0] * b[0] + b[1] * b[1]; 
        };
        
        nth_element(points.begin(), points.begin() + K, points.end(), cmp);
        // sort(points.begin(), points.end(), cmp);
        
        vector<vector<int>> ans(points.begin(), points.begin() + K);
        return ans;
    }
};

English Version in Youtube
中文版解答Youtube Link
中文版解答Bilibili Link