Medium

题目描述

给你一个长度为 n 的整数数组 nums，其中 n 是 3 的倍数，以及一个正整数 k。

将数组 nums 分成 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,2],[4,5,5],[5,5,7],[7,8,8],[9,9,10],[11,12,12]]
解释：每个数组中任意两个元素的差值都小于或等于 14。

提示：

  • n == nums.length
  • 1 <= n <= 10^5
  • n 是 3 的倍数
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= 10^5

解题思路

这道题使用贪心算法求解。核心思路是：先排序，然后将相邻的三个元素分为一组。

分析过程：

  1. 排序的必要性：为了使每组内元素差值尽可能小，我们需要将数组排序，这样相邻元素的差值最小。

  2. 贪心策略：排序后，贪心地将每连续的3个元素分为一组。如果一组中最大值和最小值的差超过k，说明无解。

  3. 正确性证明：

    • 对于排序后的数组，如果 a ≤ b ≤ c 是连续的三个元素，那么 c - a 是这三个元素中任意两个的最大差值
    • 如果连续三个元素无法满足条件，那么任何其他分组方式都不可能更优

  4. 算法步骤：

    • 对数组排序
    • 每次取3个连续元素作为一组
    • 检查每组的最大差值是否 ≤ k
    • 如果所有组都满足条件，返回结果；否则返回空数组

时间复杂度：O(n log n)，主要是排序的复杂度 空间复杂度：O(1)，不考虑输出空间的话

代码实现

class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        
        vector<vector<int>> result;
        int n = nums.size();
        
        for (int i = 0; i < n; i += 3) {
            if (nums[i + 2] - nums[i] > k) {
                return {};
            }
            result.push_back({nums[i], nums[i + 1], nums[i + 2]});
        }
        
        return result;
    }
};

class Solution:
    def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
        nums.sort()
        
        result = []
        n = len(nums)
        
        for i in range(0, n, 3):
            if nums[i + 2] - nums[i] > k:
                return []
            result.append([nums[i], nums[i + 1], nums[i + 2]])
        
        return result

public class Solution {
    public int[][] DivideArray(int[] nums, int k) {
        Array.Sort(nums);
        
        var result = new List<int[]>();
        int n = nums.Length;
        
        for (int i = 0; i < n; i += 3) {
            if (nums[i + 2] - nums[i] > k) {
                return new int[0][];
            }
            result.Add(new int[] {nums[i], nums[i + 1], nums[i + 2]});
        }
        
        return result.ToArray();
    }
}

var divideArray = function(nums, k) {
    nums.sort((a, b) => a - b);
    
    const result = [];
    const n = nums.length;
    
    for (let i = 0; i < n; i += 3) {
        if (nums[i + 2] - nums[i] > k) {
            return [];
        }
        result.push([nums[i], nums[i + 1], nums[i + 2]]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要是排序的时间复杂度，遍历数组的时间为 O(n)
空间复杂度O(1)不考虑输出空间，只使用了常数级别的额外空间