题目描述
给你一个长度为 n 的整数数组 nums，以及一个正整数 k 。
将这个数组划分为 n / 3 个长度为 3 的子数组，并满足以下条件：
- 子数组中 任意 两个元素的差必须 小于或等于
k 。
返回一个 二维数组 ，包含所有的子数组。如果不可能满足条件，就返回一个空数组。如果有多个答案，返回 任意一个 即可。
示例 1：
输入：nums = [1,3,4,8,7,9,3,5,1], k = 2
输出：[[1,1,3],[3,4,5],[7,8,9]]
解释：
每个数组中任何两个元素之间的差小于或等于 2。
示例 2：
输入：nums = [2,4,2,2,5,2], k = 2
输出：[]
解释：
将 nums 划分为 2 个长度为 3 的数组的不同方式有：
- [[2,2,2],[2,4,5]] （及其排列）
- [[2,2,4],[2,2,5]] （及其排列）
因为有四个 2，所以无论我们如何划分，都会有一个包含元素 2 和 5 的数组。因为 5 - 2 = 3 > k，条件无法被满足，所以没有合法的划分。
示例 3：
输入：nums = [4,2,9,8,2,12,7,12,10,5,8,5,5,7,9,2,5,11], k = 14
输出：[[2,2,12],[4,8,5],[5,9,7],[7,8,5],[5,9,10],[11,12,2]]
解释：
每个数组中任何两个元素之间的差小于或等于 14。
提示：
n == nums.length1 <= n <= 105n 是 3 的倍数1 <= nums[i] <= 1051 <= k <= 105
解法
方法一：排序
我们先对数组进行排序，然后每次取出三个元素，如果这三个元素的最大值和最小值的差大于 \(k\)，则无法满足条件，返回空数组。否则，我们将这三个元素组成的数组加入答案数组中。
时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组的长度。
| class Solution:
def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
nums.sort()
ans = []
n = len(nums)
for i in range(0, n, 3):
t = nums[i : i + 3]
if t[2] - t[0] > k:
return []
ans.append(t)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution {
public int[][] divideArray(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int[][] ans = new int[n / 3][];
for (int i = 0; i < n; i += 3) {
int[] t = Arrays.copyOfRange(nums, i, i + 3);
if (t[2] - t[0] > k) {
return new int[][] {};
}
ans[i / 3] = t;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public:
vector<vector<int>> divideArray(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int n = nums.size();
for (int i = 0; i < n; i += 3) {
vector<int> t = {nums[i], nums[i + 1], nums[i + 2]};
if (t[2] - t[0] > k) {
return {};
}
ans.emplace_back(t);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12 | func divideArray(nums []int, k int) [][]int {
sort.Ints(nums)
ans := [][]int{}
for i := 0; i < len(nums); i += 3 {
t := slices.Clone(nums[i : i+3])
if t[2]-t[0] > k {
return [][]int{}
}
ans = append(ans, t)
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12 | function divideArray(nums: number[], k: number): number[][] {
nums.sort((a, b) => a - b);
const ans: number[][] = [];
for (let i = 0; i < nums.length; i += 3) {
const t = nums.slice(i, i + 3);
if (t[2] - t[0] > k) {
return [];
}
ans.push(t);
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution {
func divideArray(_ nums: [Int], _ k: Int) -> [[Int]] {
var sortedNums = nums.sorted()
var ans: [[Int]] = []
for i in stride(from: 0, to: sortedNums.count, by: 3) {
if i + 2 >= sortedNums.count {
return []
}
let t = Array(sortedNums[i..<i+3])
if t[2] - t[0] > k {
return []
}
ans.append(t)
}
return ans
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | impl Solution {
pub fn divide_array(mut nums: Vec<i32>, k: i32) -> Vec<Vec<i32>> {
nums.sort();
let mut ans = Vec::new();
let n = nums.len();
for i in (0..n).step_by(3) {
if i + 2 >= n {
return vec![];
}
let t = &nums[i..i+3];
if t[2] - t[0] > k {
return vec![];
}
ans.push(t.to_vec());
}
ans
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | public class Solution {
public int[][] DivideArray(int[] nums, int k) {
Array.Sort(nums);
List<int[]> ans = new List<int[]>();
for (int i = 0; i < nums.Length; i += 3) {
if (i + 2 >= nums.Length) {
return new int[0][];
}
int[] t = new int[] { nums[i], nums[i + 1], nums[i + 2] };
if (t[2] - t[0] > k) {
return new int[0][];
}
ans.Add(t);
}
return ans.ToArray();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution {
List<List<int>> divideArray(List<int> nums, int k) {
nums.sort();
List<List<int>> ans = [];
for (int i = 0; i < nums.length; i += 3) {
if (i + 2 >= nums.length) {
return [];
}
List<int> t = nums.sublist(i, i + 3);
if (t[2] - t[0] > k) {
return [];
}
ans.add(t);
}
return ans;
}
}
|