原文链接: https://leetcode-cn.com/problems/minimum-number-of-operations-to-make-array-continuous

英文原文

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

中文题目

给你一个整数数组 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

通过代码

高赞题解

考虑最多可以保留多少个元素不变。由于元素的位置不影响答案，且要求所有元素互不相同，我们可以将 $\textit{nums}$ 排序，并去掉重复元素。

对排序去重后的 $\textit{nums}’$ 中的一段区间 $[l,r]$，若要保留这段区间内的所有元素，我们需要替换区间外的元素，填充到 $[\textit{nums}’[l],\textit{nums}’[r]]$ 内缺失的元素上。

需要填充的元素个数为

$$\textit{nums}’[r]-\textit{nums}’[l]+1-(r-l+1)$$

记原数组长度为 $n$，则区间外有 $n-(r-l+1)$ 个元素可以用来填充。由于区间外的元素个数不能少于需要填充的元素个数，所以有

$$
\textit{nums}’[r]-\textit{nums}’[l]+1-(r-l+1) \le n-(r-l+1)
$$

上式可化简为

$$
\textit{nums}’[l]\ge\textit{nums}’[r]-n+1
$$

根据该式，我们可以枚举 $\textit{nums}’[r]$，二分（或者用双指针）得到最小的满足该式的 $l$，此时 $[l,r]$ 区间内的元素均可以保留。用 $n$ 减去最多可以保留的元素个数，就是答案。

func minOperations(nums []int) (ans int) {
	n := len(nums)
	sort.Ints(nums)
	nums = unique(nums)
	for r, v := range nums {
		l := sort.SearchInts(nums[:r], v-n+1)
		ans = max(ans, r-l+1) // [l,r] 内的元素均可以保留
	}
	return n - ans
}

// 原地去重
func unique(a []int) []int {
	k := 0
	for _, v := range a[1:] {
		if a[k] != v {
			k++
			a[k] = v
		}
	}
	return a[:k+1]
}

func max(a, b int) int {
	if b > a {
		return b
	}
	return a
}

统计信息

通过次数	提交次数	AC比率
1550	3713	41.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言