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: Sliding Window
Remove duplicates and sort the numbers.
Try using nums[i] as the min number of the final array.
window [i, j), max – min < n, then change the rest of array to fit into or append after the window, which takes n – (j – i) steps.
e.g. input = [10, 3, 1, 4, 5, 6, 6, 6, 11, 15] => sorted + unique => [1, 3, 4, 5, 6, 10, 11, 15]
n = 10, window = [3, 4, 5, 6, 10, 11], max = 11, min = 3, max – min = 8 < 10
Final array = [3, 4, 5, 6, 1->7, 62->8, 63->9, 10, 11, 15->12]
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: int minOperations(vector<int>& A) { const int n = A.size(); sort(begin(A), end(A)); A.erase(unique(begin(A), end(A)), end(A)); int ans = INT_MAX; for (int i = 0, j = 0, m = A.size(); i < m; ++i) { while (j < m && A[j] < A[i] + n) ++j; ans = min(ans, n - (j - i)); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment