推 JIWP: 大師 02/01 12:41
https://leetcode.com/problems/divide-array-into-arrays-with-max-difference/description
2966. Divide Array Into Arrays With Max Difference
給你一個大小為 n 的陣列和一個數字 k，其中 n 為三的倍數，我們需把該陣列切分成多
個大小為3的子陣列，所有子陣列都需滿足所有元素的差不超過k，如果無法切分則返回空
陣列。
思路：
1.我們只需要把陣列的所有元素排序，並每次抓三個元素變成一個子陣列即可，因為相鄰
的元素差可以盡可能的小。
2.排序方面使用計數排序，如果子陣列第一個元素超出k的範圍可以提早返回。
Java Code：
---------------------------------------------------
class Solution {
public int[][] divideArray(int[] nums, int k) {
int[] count = new int[100001];
for (int num : nums) {
count[num]++;
}
int[][] res = new int[nums.length / 3][3];
int currentNum = 1;
int r = 0;
int c = 0;
while (r < res.length) {
if (count[currentNum] == 0) {
currentNum ++;
continue;
}
res[r][c++] = currentNum;
if (currentNum - res[r][0] > k) {
return new int[0][];
}
if (res[r][2] != 0) {
r++;
c = 0;
}
count[currentNum]--;
}
return res;
}
}
---------------------------------------------------
--
https://i.imgur.com/AhrL1pB.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1706762190.A.4C6.html
※ 編輯: Rushia (122.100.73.13 臺灣), 02/01/2024 12:38:26