遇到一个最优分组的问题，求解答。
给出一个长度为 n的数组和一个数字k你需要在数组中选出一些数字，这些数字两两之间的差值不能超过 k。你需要判断最多能够挑出的数字个数。（n 在 [1,100000] 之间，k 和数组中的数字在 [1，1000000000] 之间）输入数组长度 n；选出的两数字最大差值 k；和一个长度为 n 的数组。输出最多能够选出的数字个数。
展开
收起
1
条回答
写回答
写回答
-
当面对一组数字时，他们中最大的值和最小的值的差值如果不超过k，那么其中任何两个数字的差值，都一定不超过k。而有序数组，恰恰可以帮我们快速找到任何一组数字中的最大的值和最小的值，我们可以用一对指针，用右指针指向的值，与左指针指向的值做差，从而一次性判断左右指针之间的值组成的一组数，是否满足上面的条件。当右指针与左指针的差值超过 k 时，我们可以尝试移动左指针，重新满足上面的条件。当右指针与左指针的差值不超过 k 时，我们可以尝试移动右指针，寻找所求值的最大值。试着应用上面的思想，最佳方案应该可以达到：最坏情况下两个指针各遍历一次数组， 因此输入：5 5 [13,4,6,9,20] 输出：3
2021-12-23 18:45:14赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
