跳转至

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

题目描述

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

解法

方法一：排序

我们先对数组进行排序，然后每次取出三个元素，如果这三个元素的最大值和最小值的差大于 $k$，则无法满足条件，返回空数组。否则，我们将这三个元素组成的数组加入答案数组中。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是数组的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

评论