140. At Most Twice
A library keeps a shelf list of catalogue numbers in the array nums. The same number may appear many times because of duplicate copies, but the shelf only has room for at most two copies of any single catalogue number.
Return the shelf list as a new array: the catalogue numbers of nums in non-decreasing order, where every value is kept at most twice and any further copies of that value are dropped. For example, a value occurring five times appears twice in the answer, a value occurring once appears once. The input array can be in any order and may be left unchanged.
Example 1
- Input:
- nums = [4,1,4,4,2,1,4]
- Output:
- [1,1,2,4,4]
- Explanation:
Sorted the list is 1,1,2,4,4,4,4. The value 4 occurs four times and keeps two copies, giving [1,1,2,4,4].
Example 2
- Input:
- nums = [-3,7,-3,0]
- Output:
- [-3,-3,0,7]
- Explanation:
Sorted: -3,-3,0,7. Nobody appears more than twice, so everything is kept.
Example 3
- Input:
- nums = [9,9,9]
- Output:
- [9,9]
- Explanation:
Three copies of 9 are cut down to two.
Constraints
1 ≤ nums.length ≤ 105
-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 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)