Question

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

English Version

题目描述

给你一个长度为 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.length
• 1 <= n <= 105
• n 是 3 的倍数
• 1 <= nums[i] <= 105
• 1 <= 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

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;
  }
}

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;
  }
};

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
}

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;
}