LeetCode python----- 703.数据流中的第K大元素

布满荆棘的人生 2022-05-10 13:33 105阅读 0赞

# [寻找数组中的第K大的元素，多种解法以及分析][K] #

遇到了一个很简单而有意思的问题，可以看出不同的算法策略对这个问题求解的优化过程。  
问题：寻找数组中的第K大的元素。

最简单的想法是直接进行排序，算法复杂度是O(N\*logN)。这么做很明显比较低效率，因为不要求别的信息只要计算出第K大的元素。当然，如果在某种情况下需要频繁访问第K大的元素就可以先进行一次排序在直接得出结果。

第一种方式是这样，用选择排序，冒泡法，或者交换排序这类的排序，对前K个元素进行排序。这三种算法也许不是最快的排序算法。但是都有个性质：计算出最大（小）的元素的算法复杂度是O(N)。这个过程不能中断，要计算第三大的元素必须建立在已经算出第二大的元素的基础上（因为每次都是计算当前数组最大）。所以它的算法复杂度是O(N\*K);

第二种方法是用快速排序的思想。快速排序每次把一个元素交换到正确的位置，同时把左边的都方上大的，右边都放上小的。这个算法每一次选取一个枢纽元，排序之后，查看枢纽元的位置。如果它的位置大于K，就说明，要求出前面一个子序列的第K大的元素。反之，如果小于K，就说明要求出在后面一个序列的第K - 前一个序列的长度个元素。

如此，就把这个问题改变成了一个可以用快排思想解决的问题。对于快速排序，算法复杂度是O(N\*logN)。而这个算法的算法复杂度是O(N)。为什么呢？

其实这个地方的算法复杂度分析很有意思。第一次交换，算法复杂度为O(N)，接下来的过程和快速排序不同，快速排序是要继续处理两边的数据，再合并，合并操作的算法复杂度是O(1)，于是总的算法复杂度是O(N\*logN)（可以这么理解，每次交换用了N，一共logN次）。但是这里在确定枢纽元的相对位置（在K的左边或者右边）之后不用再对剩下的一半进行处理。也就是说第二次插入的算法复杂度不再是O(N)而是O(N/2)，这不还是一样吗？其实不一样，因为接下来的过程是1+1/2+1/4+........ < 2，换句话说就是一共是O(2N)的算法复杂度也就是O(N)的算法复杂度。

这个算法目前我在数据结构和算法书上和剑指Offer上都看到过。算是一种很经典很经典的算法。原因是因为他通过努力把算法复杂度在每次递归中下降一些，最终让整个算法的复杂度下降极多，算是一种十分聪明的做法。

第三种方法很是简单，但是使用它需要某个条件，也就是输入数组的取值范围很小，最好的情况是能形成完全分布，也就是1000大小的数组里面的数字是从1到1000这样子。首先，生成一个能够完全装下原数组的数组，这个地方的装下是指数组大小等于原数组最大元素（也许还有优化，但这么描述简单一点），比如原数组是\[1,2,3,4,5\],我要生成的数组大小是5，如果原数组是\[5,3,6,10\]，我要生成的数组大小是10。接下来遍历原数组，把每一个元素放到第二个数组对应的下标处，5就放在下标为5的地方（实际过程中要减1，因为是数组从0开始）。放的过程中增加元素值用来统计这个元素出现的次数。这一过程算法复杂度是O(N)。接下来，再遍历生成的数组，找出第K大的元素。  
这个过程的算法复杂度是多少呢？其实这个和原数组很有关系，原数组越离散也就越糟糕。比如原数组是\[1,1000\]，这样就十分糟糕。第二部的算法复杂度是O(M)，M是前数组的最大值。总的算法复杂度O(N)+O(M);

由此可见第三种方法在这个问题的处理非常不好。虽然第三种方法限制颇多（浮点型和负数还有对原数组大小的要求），但是第三种方法的实质是一种散列。就是把原来的映射关系变成了一种反映射。也就是说如果形成了数据与地址的直接映射。但是这种映射的问题也体现的很明显，它这么做也只能算是捡了个漏子，如果输入数组稍微一边，还是一样要用hash算法计算其hash值。再把hash值映射到地址上。

第四种方法是用二叉堆来做。对大小为N的数组构建二叉堆的算法复杂度是O(N)。然后每次下滤的算法复杂度是O(logN)，一共下滤K次，算法复杂度是O(N+K\*logN)。

这种做法比较适合用来处理输入数组极大的情况，原因是如果输入数组大到不能放入内存，那么构建二叉堆（优先队列）的时候就可以只构造一个K个元素的优先队列。如果下一个元素比这个最小堆的堆顶还小就直接pass。第二个原因是算法二在对付一个极大的输入队列的时候算法复杂度的一个常数会很大。

1.  import bisect
2.  class KthLargest:
3.      def \_\_init\_\_(self, k, nums):
4.          """
5.          :type k: int
6.          :type nums: List\[int\]
7.          """
8.          self.k = k
9.          self.nums = sorted(nums)
10.     def add(self, val):
11.         """
12.         :type val: int
13.         :rtype: int
14.         """
15.         bisect.insort\_left(self.nums, val)
16.         return self.nums\[-self.k\]
17.         
18.  import heapq       
19. class KthLargest(object):
20.   
21.     def \_\_init\_\_(self, k, nums):
22.         self.nums = nums
23.         self.k = k
24.         heapq.heapify(self.nums)
25.         while len(self.nums) > k:
26.             heapq.heappop(self.nums)
27.             
28.     def add(self, val):
29.         if len(self.nums) < self.k:
30.             heapq.heappush(self.nums, val)
31.         elif val > self.nums\[0\]:
32.             heapq.heapreplace(self.nums, val)
33.         return self.nums\[0\]
34.

[K]: https://www.cnblogs.com/dsj2016/p/5500204.html