988. Make It Continuous
A shelf of n numbered tiles is described by nums. The shelf is called continuous when, after sorting, its tile numbers are n distinct integers that follow each other without gaps, such as 6, 7, 8, 9. In one operation you may take any tile and rewrite its number to any integer you like (the new number may be any integer, including values outside the current range).
Return the minimum number of operations needed to make the shelf continuous. Position does not matter, only the multiset of final numbers.
Example 1
- Input:
- nums = [4,2,5,3]
- Output:
- 0
- Explanation:
The values already form 2, 3, 4, 5 with no repeats, so no replacement is needed.
Example 2
- Input:
- nums = [10,12,14]
- Output:
- 1
- Explanation:
Keep 10 and 12 and change 14 into 11, producing 10, 11, 12 with one replacement.
Example 3
- Input:
- nums = [1,1,1]
- Output:
- 2
- Explanation:
Duplicates cannot stay: keep one 1 and change the other two into 2 and 3, for 2 replacements.
Constraints
- 1 ≤ nums.length ≤ 105
- 1 ≤ 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 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)