题目描述
给你一个整数数组 nums
。每一次操作中,你可以将 nums
中 任意 一个元素替换成 任意 整数。
如果 nums
满足以下条件,那么它是 连续的 :
nums
中所有元素都是 互不相同 的。
nums
中 最大 元素与 最小 元素的差等于 nums.length - 1
。
比方说,nums = [4, 2, 5, 3]
是 连续的 ,但是 nums = [1, 2, 3, 5, 6]
不是连续的 。
请你返回使 nums
连续 的 最少 操作次数。
思路
一个简单的想法是先去重然后排序,这样只需要考虑有序数组的最小操作次数。
这里的有序数组是去重后排序的数组,连续数组是最终操作之后变得连续的数组。
那么怎样操作才能使操作次数最小呢?思考一下,数组中的数都有可能是最终的连续数组中的数字,既然这样,我们可以通过滑动窗口去寻找在连续数组范围里的数字。
举个例子,假设这个有序数组是 [1, 3, 5, 7, 8, 9, 11, 13]
,它的长度是 8,假设 1 是连续数组中的最小值,那么最大值就只能是 8。那么我们可以去在有序数组中找比 8 大的数字,修改它们即可。假如 1 是最小值的话,那么我们需要修改 3 次。
对于其他数字也是一样,抽象一下,假设数组 A
的长度为 l
,在我们遍历到 A
的第 i
个数字时,按照我们上面的算法,最大值应该是 A[i]+l-1
。
那么我们就可以向右找到不大于 A[i]+l-1
的最大数字 A[j]
,这样不需要修改的数字就是从 A[i]
到 A[j]
的一共 j-i+1
个数字,需要修改的和数字就是 l-(j-i+1)
个数字。
最终代码:
想得太多
这一份代码会 TLE,为什么?看一下官和官方答案的区别:
在官方的循环中没有在每次循环时给 j
赋值,而是随着 i
的增长,j
也在慢慢增长(而没有回溯),为什么可以这样做呢?好像还是蛮显然的,j
扩展到的位置表示之前的数字都在范围内,因此循环下一个 i
的时候范围不会变化,因此不需要回溯 j
了。
为了修改代码,我们把 j
的赋值挪到上面就行了:
这样的话,之前的代码时间复杂度是 O(n2),而后面的代码时间复杂度只有 O(nlog(n))。