591. Halve the Array
A warehouse holds a row of crates, and the integer nums[i] is the type code printed on crate i. To free up floor space the manager will pick a set of type codes and haul away every crate whose code is in that set; crates of a chosen type can never be left behind partially.
Return the smallest number of different type codes that must be chosen so that at least half of all the crates are hauled away, that is, the number of removed crates multiplied by 2 is at least nums.length. The answer always exists, because choosing every type removes everything. Aim for O(n log n) time and O(n) extra space.
Example 1
- Input:
- nums = [4,4,9,9,9,2,7,7]
- Output:
- 2
- Explanation:
Choosing only code 9 removes 3 of 8 crates, but adding code 4 (or 7) removes 5, which is at least half, so 2 types are needed.
Example 2
- Input:
- nums = [6,6,6,6,1]
- Output:
- 1
- Explanation:
Code 6 alone covers 4 of the 5 crates, which is more than half, so one type suffices.
Example 3
- Input:
- nums = [10,20,30,40]
- Output:
- 2
- Explanation:
Every code occurs once, so two types are needed to remove 2 of 4 crates.
Constraints
1 ≤ nums.length ≤ 200000-109 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)