Posts tagged as “sorting”

We have a list of points on the plane.  Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

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]] (The answer [[-2,4],[3,3]] would also be accepted.)

Note:

1. 1 <= K <= points.length <= 10000
2. -10000 < points[i][0] < 10000
3. -10000 < points[i][1] < 10000

Solution: Sort

Time complexity: O(nlogn)
Space complexity: O(n)

Problem

Given an array of integers A with even length, return true if and only if it is possible to reorder it such that A[2 * i + 1] = 2 * A[2 * i] for every 0 <= i < len(A) / 2.

Example 1:

Input: [3,1,3,6]
Output: false


Example 2:

Input: [2,1,2,6]
Output: false


Example 3:

Input: [4,-2,2,-4]
Output: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].


Example 4:

Input: [1,2,4,16,8,4]
Output: false


Note:

1. 0 <= A.length <= 30000
2. A.length is even
3. -100000 <= A[i] <= 100000

Solution 1:

Time complexity: O(N + 100000 * 2)

Space complexity: O(100000 * 2)

Solution 2:

Time complexity: O(NlogN)

Space complexity: O(N)

Problem

Given two arrays A and B of equal size, the advantage of A with respect to B is the number of indices i for which A[i] > B[i].

Return any permutation of A that maximizes its advantage with respect to B.

Example 1:

Input: A = [2,7,11,15], B = [1,10,4,11]
Output: [2,11,7,15]


Example 2:

Input: A = [12,24,8,32], B = [13,25,32,11]
Output: [24,32,8,12]


Note:

1. 1 <= A.length = B.length <= 10000
2. 0 <= A[i] <= 10^9
3. 0 <= B[i] <= 10^9

Solution: Greedy 田忌赛马

Use the smallest unused number A[j] in A such that A[j] > B[i], if not possible, use the smallest number in A.

Time complexity: O(nlogn)

Space complexity: O(n)

C++

Problem:

https://leetcode.com/problems/intersection-of-two-arrays/description/

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1]nums2 = [2, 2], return [2].

Note:

• Each element in the result must be unique.
• The result can be in any order.

C++ using std::set_intersection

C++ hashtable

Problem:

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: “Gold Medal”, “Silver Medal” and “Bronze Medal”.

Example 1:

Note:

1. N is a positive integer and won’t exceed 10,000.
2. All the scores of athletes are guaranteed to be unique.

Solution 1: Sorting ( + Binary Search)

C++

Mission News Theme by Compete Themes.