Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者ZooseWu (動物園公告)時間2年前 (2023/10/13 21:21)推噓-1(0推 1噓 2→)

留言3則, 2人參與討論串447/719 (看更多)

※ 引述《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 -- Zoosewu Yoututbe顯示PTT推文可以在各個網站追實況或Live時使用預覽圖: https://i.imgur.com/ZhtXdAJ.png