V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
Richard14
V2EX  ›  问与答

排序算法问题,如何快速筛选出数组前 N 位的位置?

  •  
  •   Richard14 · 2022-06-16 22:55:33 +08:00 · 1334 次点击
    这是一个创建于 651 天前的主题,其中的信息可能已经有所发展或是发生改变。

    生产中需要用到相关实现算法,感觉比较像一道算法题,但我想了想没有什么太好的办法,来请教一下万能的 v 友。

    现有一自然数 N ,假定取值范围 1-100.

    有一数组,储存双精度浮点数,数组长度为 N-100000.求筛选数组中最大(或最小)前 N 位数所在的位置。

    为传统算法基本上都是为全排序设计的,不存在说只取前 N 位最大即可。还有一个问题是排序大多数直接操作数据而不是操作指针,给我整不会了。。

    需要时间复杂度最优,不在意空间复杂度。。

    12 条回复    2022-06-17 11:13:01 +08:00
    vance123
        1
    vance123  
       2022-06-16 23:00:43 +08:00 via Android
    关键词 heap
    ipwx
        2
    ipwx  
       2022-06-16 23:01:02 +08:00   ❤️ 1
    快速选择,做一半的快速排序,期望复杂度 O(n)

    先做一次快速排序,若轴枢元素是第 K 大。

    * 如果 K < N 则对右侧做 N-K 的快速划分。
    * 如果 K > N 则对左侧做 N 的快速划分。
    per
        3
    per  
       2022-06-16 23:01:13 +08:00 via iPhone
    最大(小)堆排序
    ipwx
        4
    ipwx  
       2022-06-16 23:02:57 +08:00
    哦最大最小堆也挺好,可以处理在线情况。

    换个几号吧,如果你的全数组长度是 M ,用最小堆找最大的前 N 个元素,那么时间复杂度就是 O(M log N)。
    反之用最大堆可以找最小的 N 个元素。
    ynyounuo
        5
    ynyounuo  
       2022-06-16 23:05:08 +08:00 via iPhone
    经典 topk 算法不是全网各处都有
    dbsquirrel
        6
    dbsquirrel  
       2022-06-16 23:05:55 +08:00 via iPhone
    Quick Select?
    sunjourney
        7
    sunjourney  
       2022-06-17 00:47:06 +08:00
    大顶堆不就是吗,最常见的算法
    msg7086
        8
    msg7086  
       2022-06-17 06:04:53 +08:00
    容量 N 的大顶堆。要带位置的话元素里加上位置信息即可。
    rabbbit
        9
    rabbbit  
       2022-06-17 08:50:22 +08:00   ❤️ 1
    堆排序
    radiocontroller
        10
    radiocontroller  
       2022-06-17 09:23:10 +08:00
    堆排序和快排,快排不稳定,最差情况 O(N^2)
    anonymousar
        11
    anonymousar  
       2022-06-17 09:53:17 +08:00   ❤️ 1
    明显 bfptr 更好 一堆说 heap 是啥意思
    Erroad
        12
    Erroad  
       2022-06-17 11:13:01 +08:00
    @anonymousar #10 没学过呗,我也第一次听说
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1737 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 16:38 · PVG 00:38 · LAX 09:38 · JFK 12:38
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.