gpt4 book ai didi

algorithm - 查找具有给定差异的对

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:04:12 26 4
gpt4 key购买 nike

给定 n、k 和 n 个整数。你如何找到差为 k 的整数对?

有一个n*log n 解决方案,但我想不通。

最佳答案

你可以这样做:

  • 对数组进行排序
  • 对于每个项目 data[i],确定其两个目标对,即 data[i]+kdata[i]-k
  • 对这两个目标的排序数组进行二分查找;如果找到,将 data[i]data[targetPos] 添加到输出。

排序在 O(n*log n) 中完成。 n 搜索步骤中的每一步都需要 2 * log n 时间来寻找目标,总时间为 O(n*log n)

关于algorithm - 查找具有给定差异的对,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22282066/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com