Re: [閒聊] 每日LeetCode

[ZooseWu (動物園 公告)]

※ 引述《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 https://i.imgur.com/WqbLNV3.png
完整介紹: https://github.com/zoosewu/PTTChatOnYoutube/tree/master/homepage
支援的網站: Youtube Twitch Holotools Niji-mado Holodex

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1697203294.A.4E7.html
噓 JIWP: 大師
→ JIWP: 按到噓抱歉
→ yam276: 過去一個禮拜起碼三四題Hard