Skip to content

Latest commit

 

History

History
131 lines (100 loc) · 3.52 KB

File metadata and controls

131 lines (100 loc) · 3.52 KB

中文文档

Description

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 equals nums.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

Solutions

Python3

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        nums = sorted(set(nums))

        ans = n
        for i, start in enumerate(nums):
            end = start + n - 1
            j = bisect_right(nums, end)
            remainLen = j - i
            ans = min(ans, n - remainLen)
        return ans

Java

class Solution {
    public int minOperations(int[] nums) {
        int N = nums.length;
        if (N == 1) return 0;
        Arrays.sort(nums);
        int M = 1;
        for (int i = 1; i < N; i++) {
            if (nums[i] != nums[i - 1])
                nums[M++] = nums[i];
        }

        int j = 0;
        int ans = N;
        for (int i = 0; i < M; i++) {
            while (j < M && nums[j] <= N + nums[i] - 1) j++;
            ans = Math.min(ans, N - j + i);
        }

        return ans;
    }
}

C++

class Solution {
public:
    int minOperations(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int End = unique(nums.begin(), nums.end()) - nums.begin();
        int n = nums.size();

        int len = 0;
        for (int i = 0; i < End; ++i) {
            int temp = upper_bound(nums.begin(), nums.begin() + End, n + nums[i] - 1) - nums.begin() - i;
            len = max(len, temp);
        }
        return n - len;
    }
};

...