划分数组并满足最大差限制

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

/*
 思路：
 1. 对数组进行排序。
 2. 使用Java Stream处理，尝试将每三个元素划分为一个子数组，并检查是否满足差值条件。
 3. 如果不能完全划分为符合条件的子数组，则返回空数组。
*/

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public List<List<Integer>> partitionArray(int[] nums, int k) {
        Arrays.sort(nums);
        List<List<Integer>> result = IntStream.range(0, nums.length / 3)
            .mapToObj(i -> Arrays.asList(nums[i * 3], nums[i * 3 + 1], nums[i * 3 + 2]))
            .collect(Collectors.toList());
        for (List<Integer> group : result) {
            if (group.get(2) - group.get(0) > k) {
                return new ArrayList<>();
            }
        }
        return result;
    }
}

该题解首先对数组进行排序，排序后的数组中相邻元素的差会是最小的。由于子数组的长度固定为3，题解采用了一个循环，步长为3，从排序后的数组中依次取出每3个元素组成子数组。在每次取出子数组时，检查子数组中的最大值和最小值的差是否大于k。如果大于k，则说明无法满足题目要求，直接返回空数组。如果所有子数组都满足条件，则将这些子数组返回。这种方法使用了贪心的策略，即尽可能地将排序后相邻的元素分配到同一个子数组中，利用排序后元素间差值最小的特性来满足差值条件。

O(n log n)

O(log n)