推 JIWP: 大師 02/01 13:00
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 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的範圍可以提早返回。
Python3 Code：
---------------------------------------------------
class Solution:
def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
res = []
nums.sort()
for num in range(0, len(nums), 3):
if nums[num + 2] - nums[num] <= k:
res.append(nums[num:num + 3])
else:
return []
return res
---------------------------------------------------
class Solution:
def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
res = []
temp = []
for num in sorted(nums):
if not temp or num - temp[0] <= k:
temp.append(num)
else:
return []
if len(temp) == 3:
res.append(temp)
temp = []
return res
---------------------------------------------------
下面是自己寫的 上面是看別人的之後修改的 都有90%以上 還不錯
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.227.251.109 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1706763570.A.50A.html