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.
Example 1:
Input: nums = [1,3,4,8,7,9,3,5,1], k = 2
Output: [[1,1,3],[3,4,5],[7,8,9]]
Explanation: We can divide the array into the following arrays: [1,1,3], [3,4,5] and [7,8,9].
The difference between any two elements in each array is less than or equal to 2.
Note that the order of elements is not important.
Example 2:
Input: nums = [1,3,3,2,7,3], k = 3
Output: []
Explanation: It is not possible to divide the array satisfying all the conditions.
Constraints:
n == nums.length
1 <= n <= 105
n is a multiple of 3.
1 <= nums[i] <= 105
1 <= k <= 105
划分数组并满足最大差限制。
给你一个长度为 n 的整数数组 nums，以及一个正整数 k 。
将这个数组划分为一个或多个长度为 3 的子数组，并满足以下条件：
nums 中的 每个 元素都必须 恰好 存在于某个子数组中。
子数组中 任意 两个元素的差必须小于或等于 k 。
返回一个 二维数组 ，包含所有的子数组。如果不可能满足条件，就返回一个空数组。如果有多个答案，返回 任意一个 即可。
思路
题目只问是否可以划分，并不在意数组元素的是否需要保持不变，所以这里我选择对 input 数组排序。排序过后，可以每次看三个元素 nums[i], nums[i + 1], nums[i + 2]。如果 nums[i + 2] - nums[i] > k，说明当前这一行的最大元素和最小元素的差不满足题意，直接返回一个空的二维数组。如果满足题意，则还是每次看三个元素直到填满最后的二维数组。
复杂度
时间O(nlogn)
空间O(3n) - O(n)
代码
Java实现
class Solution {
public int[][] divideArray(int[] nums, int k) {
int[][] res = new int[nums.length / 3][3];
// corner case
if (nums == null || nums.length == 0) {
return new int[0][0];
}
// normal case
Arrays.sort(nums);
int m = 0;
for (int i = 2; i < nums.length; i += 3) {
if (nums[i] - nums[i - 2] <= k) {
res[m] = new int[] { nums[i - 2], nums[i - 1], nums[i] };
m++;
} else {
return new int[0][0];
}
}
return res;
}
}