※ 引述《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