※ 引述《yam276 (史莱哲林的优等生)》之铭言：
: 2009. Minimum Number of Operations to Make Array Continuous
: 计算把一个阵列变成连续阵列，以及：
: 1. 没有重复数字
: 2. 最大值减最小值为nums.len() -1
: 所需要的次数
: 题目描述写得有点烂
: 实际例子可以看：
: nums = [4, 2, 5, 3] 是连续阵列
: nums = [1, 2, 3, 5, 6] 不是连续阵列 要改成 [1, 2, 3, 5, 4]
难得每日会出现hard题目 当天没看到现在补交作业
first think:
定义一个类别
包含这个数字的最小边界跟最大边界还有元素
interface continueArrayData {
min: number
max: number
items: number[]
}
例如nums = [4, 2, 5, 3]
data[0]={
min: 4,
max: 4,
items: []
}
然后把新数字放进去的时候更新max或min确保以后的判断都在范围内
每个数字都要对整个阵列做一遍
拿去跑之后 就超时了
O(N^2)
发现时间复杂度是N^2之后
想到如果拿去排序就能共用max跟min
这样只要跑一次阵列就能直接找到答案
之后卡了一段时间一直找不到为什么自己测没问题 丢上去算就错了
找了很久才发现没有排除重复元素
弄好之后就好了
function minOperations (nums: number[]): number {
const uniqueNums: number[] = [...new Set(nums)].sort((a, b) => (a - b))
const range = nums.length
let result = nums.length
let minIndex = 0
let maxIndex = 0
for (let index = 0; index < uniqueNums.length; index++) {
const element = uniqueNums[index]
while (uniqueNums[minIndex] <= element - range) minIndex++
while (maxIndex < uniqueNums.length &&
uniqueNums[maxIndex] < element + range) maxIndex++
result = Math.min(nums.length -
Math.max(maxIndex - index, index - minIndex + 1), result)
}
return result
}
写完之后看了yam大的思路
原来我后面想的做法就是sliding window