class Solution {
public:
vector<vector<int>> divideArray(vector<int>& nums, int k) {
}
};
100161. 划分数组并满足最大差限制
给你一个长度为 n 的整数数组 nums，以及一个正整数 k 。
将这个数组划分为一个或多个长度为 3 的子数组，并满足以下条件：
nums 中的 每个 元素都必须 恰好 存在于某个子数组中。k 。返回一个 二维数组 ，包含所有的子数组。如果不可能满足条件，就返回一个空数组。如果有多个答案，返回 任意一个 即可。
示例 1：
输入：nums = [1,3,4,8,7,9,3,5,1], k = 2 输出：[[1,1,3],[3,4,5],[7,8,9]] 解释：可以将数组划分为以下子数组：[1,1,3]，[3,4,5] 和 [7,8,9] 。 每个子数组中任意两个元素的差都小于或等于 2 。 注意，元素的顺序并不重要。
示例 2：
输入：nums = [1,3,3,2,7,3], k = 3 输出：[] 解释：无法划分数组满足所有条件。
提示：
n == nums.length1 <= n <= 105n 是 3 的倍数1 <= nums[i] <= 1051 <= k <= 105原站题解
python3 解法, 执行用时: 168 ms, 内存消耗: 31.5 MB, 提交时间: 2023-12-17 23:38:00
'''
排序后切分
注意本题的子数组不要求是连续的。
既然元素的顺序并不重要，我们应当尽量把相近的数字都放在一起。
所以把数组排序后，从小到大三个三个地切分即可。
'''
class Solution:
def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
nums.sort()
ans = []
for i in range(2, len(nums), 3):
if nums[i] - nums[i - 2] > k:
return []
ans.append(nums[i - 2: i + 1])
return ans
java 解法, 执行用时: 25 ms, 内存消耗: 55.3 MB, 提交时间: 2023-12-17 23:38:16
public class Solution {
public int[][] divideArray(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int[][] ans = new int[n / 3][3];
for (int i = 2; i < n; i += 3) {
if (nums[i] - nums[i - 2] > k) {
return new int[][]{};
}
ans[i / 3] = new int[]{nums[i - 2], nums[i - 1], nums[i]};
}
return ans;
}
}
cpp 解法, 执行用时: 152 ms, 内存消耗: 112.4 MB, 提交时间: 2023-12-17 23:38:32
class Solution {
public:
vector<vector<int>> divideArray(vector<int> &nums, int k) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for (int i = 2; i < nums.size(); i += 3) {
if (nums[i] - nums[i - 2] > k) {
return {};
}
ans.push_back({nums[i - 2], nums[i - 1], nums[i]});
}
return ans;
}
};
golang 解法, 执行用时: 152 ms, 内存消耗: 14.7 MB, 提交时间: 2023-12-17 23:39:05
func divideArray(nums []int, k int) (ans [][]int) {
slices.Sort(nums)
for i := 2; i < len(nums); i += 3 {
if nums[i]-nums[i-2] > k {
return nil
}
ans = append(ans, nums[i-2:i+1])
}
return
}