Gives you an array of integers nums. In each operation, you can replace any element in nums with an arbitrary integer.
Nums is continuous if it satisfies the following conditions:
All elements in nums are distinct from each other.
The difference between the largest and smallest elements in nums is equal to numslength - 1 。
For example, nums = [4, 2, 5, 3] is continuous, but nums = [1, 2, 3, 5, 6] is not continuous.
Please return the minimum number of operations to make nums consecutive.
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 turn the last element into 4.
The resulting array is [1,2,3,5,4] and is a continuous array.
Example 3: Input: nums = [1,10,100,1000].
Output: 3 Explanation: A possible solution is:
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] and is a continuous array.
Hint:
1 <= nums.length <= 105Bipartite since the final array length must be the original array length. So the problem asks us to find the least operand, which is actually equivalent to finding the maximum number of unchanged numbers, so that we can make the array continuous with the least operands.1 <= nums[i] <= 109
The naïve idea is to enumerate all the intervals [a,b], where a and b are the two numbers in the intervals [min(nums),max(nums)]. The time complexity of this idea is $o(v 2)$, where v is the range of nums. Looking at the data range, it's clear that there will be a timeout.
We can sort the array first, so that we can find the answer in two parts, so that the time complexity is reduced. Looking at the time of time complexity sorting is allowable, so this solution can ac.
Specifically: deduplication of arrays traverses nums for array sorting, and for each num we binorate the leftmost and rightmost numsIndexes that satisfy a range of values with a range difference less than or equal to old nwhere old n is the length of nums before deduplication. To put it simply, we need to find the interval where the satisfying value is in the leftmost x of the [x,num] range and the satisfying value is in the rightmost y of the [num,y] range, and we find the interval that satisfies the range of the two ranges, then the maximum value of the length of the answer interval, which is n - in the length of the intervalMinimumPlease refer to ** below.
Thinking in reverse, the problem is to find the least operand, in fact, it is to find the maximum number of numbers to be retained Language support: python3
import bisectclass solution: def minoperations(self, nums: list[int]) int: ans = on = len(nums) nums = list(set(nums)) nums.sort() n = len(nums) for i, v in enumerate(nums): r = bisect.bisect_right(nums, v + on - 1) l = bisect.bisect_left(nums, v - on + 1) ans = min(ans, n - r - i), n - i - l + 1)) return ans + on - n)Let n be the length of the array.
Time complexity: $o(nlogn)$Space complexity: $o(n)$