潮州做网站,湖北省建设人力资源网站,大连金州开发区,返利网站方案LeetCode 2966. 将数组分成差值不超过 k 的长度为 3 的子数组 原题链接#xff1a;LeetCode CN - Divide Array Into Arrays With Max Difference 题目描述
给你一个整数数组 nums 和一个正整数 k。
你需要将这个数组划分为 n / 3 个长度为 3 的子数组。每个子数组必须满足LeetCode CN - Divide Array Into Arrays With Max Difference 题目描述
给你一个整数数组 nums 和一个正整数 k。
你需要将这个数组划分为 n / 3 个长度为 3 的子数组。每个子数组必须满足
子数组中任意两个元素之间的差值绝对值都 小于等于 k 要求返回这些子数组的列表二维数组形式。 如果无法划分满足条件的子数组返回空数组 []。 若有多个解返回任意一个即可。 示例分析
示例 1
输入nums [1,3,4,8,7,9], k 3
输出[[1,3,4],[7,8,9]]解释
排序后[1,3,4,7,8,9]
分组
- [1,3,4] 差值最大为 3
- [7,8,9] 差值最大为 2 示例 2
输入nums [1,3,4], k 1
输出[]
解释1 和 3 差为 2超过了 1思路解析
本质分析
我们需要把数组分成若干组每组正好 3 个元素且这 3 个元素两两差值都 k。
解法排序 贪心分组
步骤 判断 nums.size() % 3 ! 0无法整除直接返回 [] 对数组进行排序 每隔 3 个数组成一个子数组 [a,b,c]只需检查 c - a k因为排序后a b c最大差值在 a 和 c 之间 若所有子数组都满足条件返回所有子数组 若任意一组不满足返回 []
为什么只需判断 max - min k
因为排序后
差值最大的一对是 最小值 和 最大值若 max - min k则中间那个值也自然合法 代码实现
C 实现
class Solution {
public:vectorvectorint divideArray(vectorint nums, int k) {int n nums.size();if (n % 3 ! 0) return {};sort(nums.begin(), nums.end());vectorvectorint res;for (int i 0; i n; i 3) {if (nums[i 2] - nums[i] k) {return {};}res.push_back({nums[i], nums[i 1], nums[i 2]});}return res;}
};Go 实现
import sortfunc divideArray(nums []int, k int) [][]int {n : len(nums)if n%3 ! 0 {return [][]int{}}sort.Ints(nums)var res [][]intfor i : 0; i n; i 3 {if nums[i2]-nums[i] k {return [][]int{}}group : []int{nums[i], nums[i1], nums[i2]}res append(res, group)}return res
}边界测试用例
输入k输出说明[1,2,3], 11[]3-12 1[1,2,3], 22[[1,2,3]]合法[10,13,11,7,8,9], 33[[7,8,9],[10,11,13]]合法[1,2,3,4], 22[]不能整除 复杂度分析 时间复杂度 排序O(n log n)分组判断O(n)总体O(n log n) 空间复杂度 排序O(1)就地排序结果数组O(n) 拓展思考
1. 如果要求每个子数组 长度为任意值但差值仍需小于等于 k
就不能使用固定步长分组了可考虑 双指针 滑动窗口
2. 如果允许的组数不确定但要最多分组
可以用贪心策略 union set 找最大匹配组 总结 这是一个 排序 分段验证 的贪心题 关键在于观察 只需判断一组的最大值和最小值差是否超过 k 若不要求固定长度为 3就需考虑滑动窗口等策略
