Hard

题目描述

给你一个整数数组 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 <= 10^5
  • 1 <= nums[i] <= 10^9

解题思路

解题思路

要使数组连续，最终数组必须是长度为 n 的连续整数序列，且所有元素唯一。我们需要找到保留最多原数组元素的方案。

核心思想是滑动窗口：

  1. 首先去重并排序，因为重复元素必须被替换
  2. 对于每个可能的起始位置 start，连续数组的范围应该是 [start, start + n - 1]
  3. 使用滑动窗口或二分查找找到这个范围内有多少个原数组中的元素
  4. 范围内的元素可以保留，其余元素需要替换

具体实现：

  • 去重排序后的数组记为 unique
  • 对每个 unique[i] 作为起始位置，计算范围 [unique[i], unique[i] + n - 1] 内的元素个数
  • 使用二分查找找到右边界，计算窗口内元素个数
  • 操作次数 = n - 窗口内元素个数
  • 取所有可能方案的最小值

时间复杂度主要来自排序 O(n log n) 和每个位置的二分查找 O(n log n)。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        
        // 去重并排序
        sort(nums.begin(), nums.end());
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        
        int minOps = n;
        
        // 对每个可能的起始位置
        for (int i = 0; i < nums.size(); i++) {
            int start = nums[i];
            int end = start + n - 1;
            
            // 二分查找第一个大于 end 的位置
            int right = upper_bound(nums.begin(), nums.end(), end) - nums.begin();
            
            // 窗口内元素个数
            int count = right - i;
            
            // 需要替换的元素个数
            minOps = min(minOps, n - count);
        }
        
        return minOps;
    }
};

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 去重并排序
        unique = sorted(set(nums))
        
        min_ops = n
        
        # 对每个可能的起始位置
        for i in range(len(unique)):
            start = unique[i]
            end = start + n - 1
            
            # 二分查找第一个大于 end 的位置
            left, right = 0, len(unique)
            while left < right:
                mid = (left + right) // 2
                if unique[mid] <= end:
                    left = mid + 1
                else:
                    right = mid
            
            # 窗口内元素个数
            count = left - i
            
            # 需要替换的元素个数
            min_ops = min(min_ops, n - count)
        
        return min_ops

public class Solution {
    public int MinOperations(int[] nums) {
        int n = nums.Length;
        
        // 去重并排序
        var unique = nums.Distinct().OrderBy(x => x).ToArray();
        
        int minOps = n;
        
        // 对每个可能的起始位置
        for (int i = 0; i < unique.Length; i++) {
            int start = unique[i];
            int end = start + n - 1;
            
            // 二分查找第一个大于 end 的位置
            int left = 0, right = unique.Length;
            while (left < right) {
                int mid = (left + right) / 2;
                if (unique[mid] <= end) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            
            // 窗口内元素个数
            int count = left - i;
            
            // 需要替换的元素个数
            minOps = Math.Min(minOps, n - count);
        }
        
        return minOps;
    }
}

var minOperations = function(nums) {
    const n = nums.length;
    
    // 去重并排序
    const unique = [...new Set(nums)].sort((a, b) => a - b);
    
    let minOps = n;
    
    // 对每个可能的起始位置
    for (let i = 0; i < unique.length; i++) {
        const start = unique[i];
        const end = start + n - 1;
        
        // 二分查找第一个大于 end 的位置
        let left = 0, right = unique.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (unique[mid] <= end) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // 窗口内元素个数
        const count = left - i;
        
        // 需要替换的元素个数
        minOps = Math.min(minOps, n - count);
    }
    
    return minOps;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n log n)排序 O(n log n)，二分查找 O(n log n)
空间复杂度O(n)去重后的数组空间

相关题目