gpt4 book ai didi

algorithm - 查找n元素数组中某个元素是否出现n/4次

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:32:49 25 4
gpt4 key购买 nike

有人问我这个问题。我尝试使用多数元素方法,但它对我不起作用。请提供一些提示。

最佳答案

  1. O(n) 时间内找出中位数。
  2. 使用三向分区根据中位数对数组进行分区。
  3. 如果 median 本身是必需的元素则完成
    否则
    在两个分区(左右中位数)上应用多数元素算法。 (在您的情况下,找到在 n/2 的数组中出现超过 n/4 次的元素)。两者都将在 O(n) 时间内运行。

总时间为 3*O(n)=O(n)
希望这会有所帮助:)

关于algorithm - 查找n元素数组中某个元素是否出现n/4次,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12038204/

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