在不排序的情况下查找数组中的第三大元素

Question

我在 python 中一遍又一遍地提出这些类似的问题。我想掌握解决这类问题的方法。请帮助我。

问题类似于“在不排序的情况下在数组中找到第三大（或第二大或有时是第 k 大）元素（或项目）”有时会出现另一个条件“具有最少的比较数”或“在准时”。我该如何接近？或者如何为此编写算法？

谢谢！

Answer 1

不想要第三大的就把n改成对应的数字

largest[0]是第n大数。

n=3
haystack=[1,2,3]
largest=[0]*n
for a in haystack:
    k=n
    for i in range(n):
        if a<=largest[i]:
            k=i
            break
    if k:
        k-=1
        for j in range(k):
            largest[j]=largest[j+1]
        largest[k]=a

Answer 2

from heapq import heapify,heappop,heappush


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        # this creates min-heap
        heapify(heap)
        for e in nums:
            #  with O(log n) push and O(log n) pop
            heappush(heap,e)
            if len(heap)>k:
                heappop(heap)
        return heappop(heap)

在不排序的情况下查找数组中的第三大元素

Find 3rd largest element in an array without sorting

python

arrays

algorithm

element

find