（数据结构与算法）现有N个数，找出其中第M大的数，这里的N远

[问答题]

（数据结构与算法）现有N个数，找出其中第M大的数，这里的N远大于M。请说明算法思路、复杂度

一吻以谢天下

建立一个容量为M的小根堆，遍历这N个元素，当前元素如果大于堆顶元素就删除堆顶元素加入此元素，这样操作后的堆容量还是M，遍历完成依次取出堆顶元素，取到的最后一个元素就是所求。

-- NORMAL --

因为需要的空间只是容量为M的堆，所以空间复杂度为O(M)

首先建立容量为M的堆得时间复杂对为O(N)

遍历到一个元素时，可能插入，也可能不插入，如果每次都插入，也就是最坏情况，插入一个元素的时间复杂度为O(log(M))，插入N个元素的时间复杂度也就是O(N*log(M))。

最后取元素的时间复杂度为M*log(M)

所以最坏时间复杂度为O(M+N*log(M))=O(N*log(M))。

发表于 2018-03-03 20:32:24 回复(0)

Spongebobmay

def sink(heap,k,heapsize):
    while 2*k+1<=heapsize:
         j = 2*k+1
          if j<=heapsize and heap[j]<heap[j+1]:
              j++
          if heap[k]>=heap[j]:
              break
          heap[k],heap[j]=heap[j],heap[k]
          k=j
def heapsort(heap):
    N = len(heap)
    for i in xrange(N/2-1,-1,-1):
        sink(heap,i,N)
    while N>1:
        heap[0],heap[N--]=heap[n],heap[0]
        sink(heap,0,N)
    M = heap[M]
    return M

菜鸟一只，用的堆排序的方法，时间复杂度是O(nlogn),建立堆的过程的时间复杂度是O(n)，而对于更改堆重建过程中，对于每个元素都要下沉，
下沉logn次，而一共有n个元素，所以此时的时间复杂度为O(nlogn)

发表于 2018-03-09 16:13:38 回复(0)