Question

2009. 使数组连续的最少操作数

English Version

题目描述

给你一个整数数组 nums 。每一次操作中，你可以将 nums 中 任意 一个元素替换成 任意 整数。

如果 nums 满足以下条件，那么它是 连续的 ：

• nums 中所有元素都是 互不相同 的。
• nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。

比方说，nums = [4, 2, 5, 3] 是 连续的 ，但是 nums = [1, 2, 3, 5, 6] 不是连续的 。

请你返回使 nums 连续 的 最少 操作次数。

 

示例 1：

输入：nums = [4,2,5,3]
输出：0
解释：nums 已经是连续的了。

示例 2：

输入：nums = [1,2,3,5,6]
输出：1
解释：一个可能的解是将最后一个元素变为 4 。
结果数组为 [1,2,3,5,4] ，是连续数组。

示例 3：

输入：nums = [1,10,100,1000]
输出：3
解释：一个可能的解是：
- 将第二个元素变为 2 。
- 将第三个元素变为 3 。
- 将第四个元素变为 4 。
结果数组为 [1,2,3,4] ，是连续数组。

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

解法

方法一：排序 + 去重 + 二分查找

我们先将数组排序，去重。

然后遍历数组，枚举以当前元素 $nums[i]$ 作为连续数组的最小值，通过二分查找找到第一个大于 $nums[i] + n - 1$ 的位置 $j$，那么 $j-i$ 就是当前元素作为最小值时，连续数组的长度，更新答案，即 $ans = \min(ans, n - (j - i))$。

最后返回 $ans$ 即可。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组长度。

class Solution:
  def minOperations(self, nums: List[int]) -> int:
    ans = n = len(nums)
    nums = sorted(set(nums))
    for i, v in enumerate(nums):
      j = bisect_right(nums, v + n - 1)
      ans = min(ans, n - (j - i))
    return ans

class Solution {
  public int minOperations(int[] nums) {
    int n = nums.length;
    Arrays.sort(nums);
    int m = 1;
    for (int i = 1; i < n; ++i) {
      if (nums[i] != nums[i - 1]) {
        nums[m++] = nums[i];
      }
    }
    int ans = n;
    for (int i = 0; i < m; ++i) {
      int j = search(nums, nums[i] + n - 1, i, m);
      ans = Math.min(ans, n - (j - i));
    }
    return ans;
  }

  private int search(int[] nums, int x, int left, int right) {
    while (left < right) {
      int mid = (left + right) >> 1;
      if (nums[mid] > x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

class Solution {
public:
  int minOperations(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int m = unique(nums.begin(), nums.end()) - nums.begin();
    int n = nums.size();
    int ans = n;
    for (int i = 0; i < m; ++i) {
      int j = upper_bound(nums.begin() + i, nums.begin() + m, nums[i] + n - 1) - nums.begin();
      ans = min(ans, n - (j - i));
    }
    return ans;
  }
};

func minOperations(nums []int) int {
  sort.Ints(nums)
  n := len(nums)
  m := 1
  for i := 1; i < n; i++ {
    if nums[i] != nums[i-1] {
      nums[m] = nums[i]
      m++
    }
  }
  ans := n
  for i := 0; i < m; i++ {
    j := sort.Search(m, func(k int) bool { return nums[k] > nums[i]+n-1 })
    ans = min(ans, n-(j-i))
  }
  return ans
}

use std::collections::BTreeSet;

impl Solution {
  #[allow(dead_code)]
  pub fn min_operations(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let nums = nums.into_iter().collect::<BTreeSet<i32>>();

    let m = nums.len();
    let nums = nums.into_iter().collect::<Vec<i32>>();

    let mut ans = n;

    for i in 0..m {
      let j = match nums.binary_search(&(nums[i] + (n as i32))) {
        Ok(idx) => idx,
        Err(idx) => idx,
      };
      ans = std::cmp::min(ans, n - (j - i));
    }

    ans as i32
  }
}

方法二：排序 + 去重 + 双指针

与方法一类似，我们先将数组排序，去重。

然后遍历数组，枚举以当前元素 $nums[i]$ 作为连续数组的最小值，通过双指针找到第一个大于 $nums[i] + n - 1$ 的位置 $j$，那么 $j-i$ 就是当前元素作为最小值时，连续数组的长度，更新答案，即 $ans = \min(ans, n - (j - i))$。

最后返回 $ans$ 即可。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组长度。

class Solution:
  def minOperations(self, nums: List[int]) -> int:
    n = len(nums)
    nums = sorted(set(nums))
    ans, j = n, 0
    for i, v in enumerate(nums):
      while j < len(nums) and nums[j] - v <= n - 1:
        j += 1
      ans = min(ans, n - (j - i))
    return ans

class Solution {
  public int minOperations(int[] nums) {
    int n = nums.length;
    Arrays.sort(nums);
    int m = 1;
    for (int i = 1; i < n; ++i) {
      if (nums[i] != nums[i - 1]) {
        nums[m++] = nums[i];
      }
    }
    int ans = n;
    for (int i = 0, j = 0; i < m; ++i) {
      while (j < m && nums[j] - nums[i] <= n - 1) {
        ++j;
      }
      ans = Math.min(ans, n - (j - i));
    }
    return ans;
  }
}

class Solution {
public:
  int minOperations(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int m = unique(nums.begin(), nums.end()) - nums.begin();
    int n = nums.size();
    int ans = n;
    for (int i = 0, j = 0; i < m; ++i) {
      while (j < m && nums[j] - nums[i] <= n - 1) {
        ++j;
      }
      ans = min(ans, n - (j - i));
    }
    return ans;
  }
};

func minOperations(nums []int) int {
  sort.Ints(nums)
  n := len(nums)
  m := 1
  for i := 1; i < n; i++ {
    if nums[i] != nums[i-1] {
      nums[m] = nums[i]
      m++
    }
  }
  ans := n
  for i, j := 0, 0; i < m; i++ {
    for j < m && nums[j]-nums[i] <= n-1 {
      j++
    }
    ans = min(ans, n-(j-i))
  }
  return ans
}