开发者社区> 问答> 正文

遇到一个最优分组的问题,求解答。

给出一个长度为 n的数组和一个数字k你需要在数组中选出一些数字,这些数字两两之间的差值不能超过 k。你需要判断最多能够挑出的数字个数。(n 在 [1,100000] 之间,k 和数组中的数字在 [1,1000000000] 之间)输入数组长度 n;选出的两数字最大差值 k;和一个长度为 n 的数组。输出最多能够选出的数字个数。

展开
收起
游客4skzfvnrxrzbi 2021-12-23 16:53:31 432 0
1 条回答
写回答
取消 提交回答
  • 当面对一组数字时,他们中最大的值和最小的值的差值如果不超过k,那么其中任何两个数字的差值,都一定不超过k。而有序数组,恰恰可以帮我们快速找到任何一组数字中的最大的值和最小的值,我们可以用一对指针,用右指针指向的值,与左指针指向的值做差,从而一次性判断左右指针之间的值组成的一组数,是否满足上面的条件。当右指针与左指针的差值超过 k 时,我们可以尝试移动左指针,重新满足上面的条件。当右指针与左指针的差值不超过 k 时,我们可以尝试移动右指针,寻找所求值的最大值。试着应用上面的思想,最佳方案应该可以达到:最坏情况下两个指针各遍历一次数组, 因此输入:5 5 [13,4,6,9,20] 输出:3

    2021-12-23 18:45:14
    赞同 展开评论 打赏
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载