Re: [閒聊] 每日LeetCode

[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]


思路：

用Sliding Window

方法是把無法讓window內形成連續整數的num刪除

最後每次操作更新result

讓每個循環的n-window大小(即修改次數)去比誰最小


Code:

impl Solution {
    pub fn min_operations(mut nums: Vec<i32>) -> i32 {
        let n = nums.len() as i32;
        nums.sort_unstable();
        nums.dedup();

        let mut result = n;
        let mut left = 0;

        for (right, &num) in nums.iter().enumerate() {
            while left < nums.len() && nums[left] < num + n {
                left += 1;
            }

            result = result.min(n - (left - right) as i32);
        }

        result
    }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.249.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1696945232.A.D4E.html
→ JIWP: 大師
※ 編輯: yam276 (123.193.249.242 臺灣), 10/10/2023 23:39:55