划分数组并满足最大差限制
问题描述
给定一个长度为 ( 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 - 输出：
[] - 解释：无论如何划分，都会有一个包含元素 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。
解决方案
思路
- 排序数组：首先对数组进行排序，以便于后续的分组和差值计算。
- 分组：从数组的第一个元素开始，每次取连续的三个元素作为一个子数组。
- 检查条件：对于每个子数组，检查其最大值和最小值的差是否小于或等于 ( k )。
- 返回结果：如果所有子数组都满足条件，返回这些子数组；否则，返回空数组。
代码实现
from typing import Listclass Solution:def divideArray(self, nums: List[int], k: int) -> List[List[int]]:nums.sort()temp = []n = len(nums)for i in range(0, n, 3): # 从0开始，步长为3group = nums[i:i+3]# 先检查组内最大值和最小值的差if group[2] - group[0] > k: # 排序后group[2]是最大值，group[0]是最小值return []temp.append(group)return temp
关键点
- 排序：通过排序，确保每个子数组的最大值和最小值在已知位置。
- 步长：使用步长为3的循环，确保每次取出3个元素。
- 条件检查：在添加子数组之前，检查其是否满足条件。
总结
通过对数组进行排序和分组，我们可以有效地解决这个问题。关键在于确保每个子数组的最大差值不超过给定的 ( k )。这种方法在时间复杂度上是 ( O(n \log n) )，因为排序是主要的时间消耗。
