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 a 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文章