LeetCode #2966 Divide Array Into Arrays With Max Difference 依最大值的差異分割陣列為多個陣列

這一題中,我們必須遵守一些規則來將一個陣列分割成數個子陣列~

英文原文如下

You are given an integer array nums of size n and a positive integer k.

Divide the array into one or more arrays of size 3 satisfying the following conditions:

  • Each element of nums should be in exactly one array.
  • The difference between any two elements in one array is less than or equal to k.

Return 2D array containing all the arrays. If it is impossible to satisfy the conditions, return an empty array. And if there are multiple answers, return any of them.

中文翻譯

給予你一個長度為 n 整數陣列 nums 跟一個正整數 k

將整個陣列分割成一個或多個大小為 3 的陣列,滿足以下的條件:

  • nums 中的每一個元素都應該要存在一個陣列中
  • 任一陣列中的兩個元素差值必須小於或等於 k

回傳一個包含了所有陣列的二維陣列,要是沒辦法滿足所有條件,就回傳一個空陣列。

假如有多個答案,回傳任一個即可

範例及題目限制

💡提示 1

嘗試使用貪婪法

💡提示 2

排列整個陣列,並嘗試將3個連續的元素湊為一組


解題思路

在我們的第一次嘗試中,我們先依照提示的將整個陣列排序

再來3個3個一組的來判斷第一個元素跟第三個元素差值是否在 k 以內

要是符合,就將子陣列儲存,反之則回傳空陣列~

C# 解決方案

⚠️方案1

public class Solution {
    public int[][] DivideArray(int[] nums, int k) {
        
        Array.Sort(nums);
        int[][]res = new int[nums.Length/3][];

        int curIdx = 0;
        int resCnt = 0;

        while(curIdx<nums.Length-1){
            if(nums[curIdx+2]-nums[curIdx]>k){
                return new int[0][];
            }
            int[]tmp = nums[curIdx..(curIdx+3)];

            res[resCnt] = tmp;
            resCnt++;
            curIdx+=3;
        }

        return res;
    }
}

最後經過多次提交,大致上超過了 40%的提交,代表還有可以加強的地方


結論

回頭想想其他解法再回來更新~

🧡如果這篇文章有幫上你的一點點忙,那是我的榮幸

🧡收藏文章或幫我點個廣告,那都是對我的支持

✅如有任何疑問,歡迎透過留言或messenger讓我知道 !

題目連結 : Divide Array Into Arrays With Max Difference – LeetCode

一些隨機的LeetCode文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *