算法笔试模拟题精解之“最优分组”
算法笔试模拟题精解之“最优分组”
贡献者 | 洪浩原
简介：一组数字，在不改变顺序的情况下，每相邻两个数字之间的差值是确定
的。所以可以对这组数字进行排序后遍历的方法。
题目描述
等级：容易
知识点：尺取法
查看题目：最优分组
给出一个长度为 n 的数组和一个数字 k，你需要在数组中选出一些数字，这些
数字两两之间的差值不能超过 k。你需要判断最多能够挑出的数字个数。（n 在 [1,
100000] 之间，k 和数组中的数字在 [1，1000000000] 之间）
输入数组长度 n；选出的两数字最大差值 k；和一个长度为 n 的数组。
输出最多能够选出的数字个数。
示例 1
输入：
5
5
[13,4,6,9,20]
输出：
解题方法：排序后遍历
很多同学在思考这道题的过程中，碰到最大的难点就是，一个数字可能同时属于
多个分组，而这个分组的大小，可能是从 2~n 任何一个数字。这样的组合方式，如
果用暴力的方法，挨个遍历的话，是非常恐怖的。
比如，如果这道题提供了一个长 100 的数组用例，那么选出一组数可能的组合
方式，就有 2^100 ≈ 1024^10 ≈ 10^30 种。
所以我们发现，拖累解题过程最直接的点，在于题目给的数据结构不合理。对一
个无序的，可能很长的数组，怎么可能短时间内遍历所有的“取一组数”的可能性呢？
于是，我们可以考虑，如何优化这道题提供的数据。对数组，在不违反题目要求
的情况下，最简单的优化方式就是排序。排序的时间复杂度很低，好的排序算法的空
间复杂度为常数级，对本题影响很小。所以不妨假设对于一组有序的数字，再去考虑
这道题，会不会发现简单了不少？
当面对一组数字时，他们中最大的值和最小的值的差值如果不超过 k，那么其中任
何两个数字的差值，都一定不超过 k。而有序数组，恰恰可以帮我们快速找到任何一组数
字中的最大的值和最小的值，我们可以用一对指针，用右指针指向的值，与左指针指向
的值做差，从而一次性判断左右指针之间的值组成的一组数，是否满足上面的条件。
当右指针与左指针的差值超过 k 时，我们可以尝试移动左指针，重新满足上面的
条件。
当右指针与左指针的差值不超过 k 时，我们可以尝试移动右指针，寻找所求值的
最大值。
试着应用上面的思想，最佳方案应该可以达到：最坏情况下两个指针各遍历一次
数组，就可以得到正确答案了。
时间复杂度：O(nlogn)
全站分卷索引 · 74 卷
- 1一、算法思想
- 2算法笔试模拟题精解之“打怪兽”
- 31.2 贪心
- 4算法笔试模拟题精解之“最强的团队”
- 5算法笔试模拟题精解之“Tom 爱吃巧克力”
- 6算法笔试模拟题精解之“吃奶酪”
- 7算法笔试模拟题精解之“一的个数”
- 8算法笔试模拟题精解之“Bob 的花束”
- 9算法笔试模拟题精解之“钱庄”
- 10算法笔试模拟题精解之“移动射击”
- 11算法笔试模拟题精解之“相似数组”
- 12算法笔试模拟题精解之“过吊桥”
- 13算法笔试模拟题精解之“完美排列”
- 14算法笔试模拟题精解之“采摘圣诞果”
- 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
- 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
- 17算法笔试模拟题精解之“学习小组”
- 18算法笔试模拟题精解之“恢复字符串”
- 191.3 DP/ 动态规划
- 20算法笔试模拟题精解之“寻找等比数列”
- 21算法笔试模拟题精解之“字符配对”
- 22算法笔试模拟题精解之“数组染色”
- 23算法笔试模拟题精解之“连绵的群山”
- 24算法笔试模拟题精解之“难住Tom 的问题”
- 25算法笔试模拟题精解之“变化的字符”
- 26算法笔试模拟题精解之“跳房子”
- 27算法笔试模拟题精解之“寒假活动”
- 28算法笔试模拟题精解之“最短路”
- 29算法笔试模拟题精解之“codancer 上楼”
- 30算法笔试模拟题精解之“木棒拼接”
- 31算法笔试模拟题精解之“Codancer 的数组封印”
- 32算法笔试模拟题精解之“Jerry 的异或运算”
- 33算法笔试模拟题精解之“小明的数学作业”
- 34算法笔试模拟题精解之“奇偶数列”
- 351.4 剪枝
- 361.5 尺取法
- 37算法笔试模拟题精解之“调整数组”
- 38算法笔试模拟题精解之“最优分组”
- 39算法笔试模拟题精解之“破译密码”
- 40二、数据结构
- 412.2 搜索
- 42算法笔试模拟题精解之“能量半径”
- 43算法笔试模拟题精解之“苹果收获程序”
- 44算法笔试模拟题精解之“恐怖的辐射”
- 45算法笔试模拟题精解之“树的拆分”
- 46算法笔试模拟题精解之“Password”
- 47算法笔试模拟题精解之“神奇数字在哪里”
- 48算法笔试模拟题精解之“神奇的棋子”
- 492.3 树
- 50算法笔试模拟题精解之“Codancer 的旅行”
- 51算法笔试模拟题精解之“Codancer 的求和”
- 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
- 532.4 线型
- 54算法笔试模拟题精解之“最活跃的数”
- 55算法笔试模拟题精解之“非递减序列”
- 56算法笔试模拟题精解之“Tom 跳方格”
- 57算法笔试模拟题精解之“复杂的字符串”
- 58算法笔试模拟题精解之“神秘消失”
- 59三、计算
- 60算法笔试模拟题精解之“简单题？
- 61算法笔试模拟题精解之“朋友一生一起走”
- 62算法笔试模拟题精解之“正三角塔”
- 63算法笔试模拟题精解之“组队难题”
- 64算法笔试模拟题精解之“2n 合体”
- 65算法笔试模拟题精解之“平行线”
- 66算法笔试模拟题精解之“叠叠高”
- 67算法笔试模拟题精解之“公平”
- 68算法笔试模拟题精解之“Tom 的手工课”
- 69算法笔试模拟题精解之“填数问题”
- 70算法笔试模拟题精解之“Jerry 的考验”
- 71算法笔试模拟题精解之“超车”
- 72算法笔试模拟题精解之“坏掉的时钟”
- 73算法笔试模拟题精解之“期末考试”
- 74算法笔试模拟题精解之“滑雪比赛”