Problem
You are given an integer array nums
. In one operation, you can replace any element in nums
with any integer.
nums
is considered continuous if both of the following conditions are fulfilled:
All elements in
nums
are unique.The difference between the maximum element and the minimum element in
nums
equalsnums.length - 1
.
For example, nums = [4, 2, 5, 3]
is continuous, but nums = [1, 2, 3, 5, 6]
is not continuous.
Return **the *minimum* number of operations to make nums
**continuous.
Example 1:
Input: nums = [4,2,5,3]
Output: 0
Explanation: nums is already continuous.
Example 2:
Input: nums = [1,2,3,5,6]
Output: 1
Explanation: One possible solution is to change the last element to 4.
The resulting array is [1,2,3,5,4], which is continuous.
Example 3:
Input: nums = [1,10,100,1000]
Output: 3
Explanation: One possible solution is to:
- Change the second element to 2.
- Change the third element to 3.
- Change the fourth element to 4.
The resulting array is [1,2,3,4], which is continuous.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 109
Solution
/**
* @param {number[]} nums
* @return {number}
*/
var minOperations = function(nums) {
nums.sort((a, b) => a - b);
var uniqueNums = [];
for (var i = 0; i < nums.length; i++) {
if (nums[i] !== nums[i - 1]) uniqueNums.push(nums[i]);
}
var left = 0;
var maxUniqueNumsInRange = 0;
for (var right = 0; right < uniqueNums.length; right++) {
while (uniqueNums[right] - uniqueNums[left] >= nums.length) left++;
maxUniqueNumsInRange = Math.max(maxUniqueNumsInRange, right - left + 1);
}
return nums.length - maxUniqueNumsInRange;
};
Explain:
nope.
Complexity:
- Time complexity : O(n * log(n)).
- Space complexity : O(n).