【Leetcode】- 排序系列

 1 import heapq
 2 from queue import PriorityQueue
 3 class Solution:
 4     def findKthLargest(self, nums: List[int], k: int) -> int:
 5         #方法一：利用快速排序的方式，寻找第K个位置的元素就可以了，不用完全排序
 6         # 时间复杂度：O(N)，这里 NN 是数组的长度，理由可以参考本题解下用户 @ZLW 的评论，需要使用主定理进行分析。
 7         # 空间复杂度：O(1)，原地排序，没有借助额外的辅助空间。
 8 
 9         # 作者：liweiwei1419
10         # 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/partitionfen-er-zhi-zhi-you-xian-dui-lie-java-dai-/
11         # 来源：力扣（LeetCode）
12         # 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
13         n = len(nums)
14         target = n-k 
15         start = 0 
16         end = n-1
17         while start<=end: #注意这个循环条件，因为早晚会return出去的,也可以改成while True: 不过这里我需要再想想
18             index = self.partition(nums,start,end)  #
19             if index==target:
20                 return nums[index]
21             elif target>index:
22                 start = index+1
23             else:
24                 end = index-1
25 
26     
27     def partition(self, nums, left,right):
28         if left==right:
29             return left
30         if right>left:
31             p = random.randint(left,right)
32             self.swap(nums,p,left)
33         # print('left:',left)
34         # print('right:',right)
35         povit = left 
36         i = left+1
37         while i<=right:
38             if nums[i]<nums[left]:
39                 povit+=1
40                 self.swap(nums,i,povit) #这里要注意不要写错
41             i+=1 
42         self.swap(nums,povit,left)
43         return povit 
44     def swap(self,nums,i,j):
45         tmp = nums[i]
46         nums[i] = nums[j] 
47         nums[j] = tmp
48 
49     #方法二：堆排序，这个也是需要会的
50     #关于heapq的官方文档：https://docs.python.org/zh-cn/3/library/heapq.html
51     #主要是熟悉heapq.heappush heapq.heappop heapq.heapreplace就可以了 注意这事一个类包，对应的函数输入需要一个作为list使用的,
52     #关于这个解法的链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/partitionfen-er-zhi-zhi-you-xian-dui-lie-java-dai-/
53     def findKthLargest(self, nums: List[int], k: int) -> int:
54         # step1: 使用容量为 k 的小顶堆
55         # step2: 元素个数小于 k 的时候，放进去就是了
56         # step3: 元素个数大于 k 的时候，小于等于堆顶元素，就扔掉，大于堆顶元素，就替换
57         n = len(nums)
58         h = []
59         if n<k:
60             return None 
61         for i in range(k):
62             heapq.heappush(h,nums[i])
63         for i in range(k,n):
64             if nums[i]>h[0]:
65                 heapq.heapreplace(h,nums[i])
66         return h[0]
67 
68         #堆竟然还有另外一种方式,这个更简单，但是时间复杂度会高一些，就是都加到堆中，然后判断size是不是大于k,如果是就把堆顶pop
69         
70         n = len(nums)
71         h = []
72         if n<k:
73             return None 
74         for i in range(n):
75             heapq.heappush(h,nums[i])
76             if len(h)>k:
77                 heapq.heappop(h)
78         return h[0]
79 
80 
81         # #这里还有使用优先队列的方式，q = PriorityQueue()定义的方式，然后put是插入，然后get是删除最优先的，默认最小的,但是没有找到那种只查看最有效的数字，不出队列的方法，还是及heapq吧，这个感觉有些乱
82         n = len(nums)
83         h = []
84         if n<k:
85             return None 
86         q = PriorityQueue()  #注意优先队列的实现方式
87         for i in range(n):
88             q.put(nums[i])
89             if q.qsize()>k: #
90                 q.get()  #
91         return q.get()
92 
93 
94 
95         
96 
97 
98     
99     

 1 class Solution {
 2     public int[] topKFrequent(int[] nums, int k) {
 3         //方法一:也是容易想到的方法,就是使用堆排序,其实这个思路我是想到的,但是由于对小顶堆这种不太熟悉,所以我看了答案
 4         //这道题对我来说,还是需要主要复习语法结构,太对语法结构了!!!一定要回来仔细看看,
 5         //时间复杂度:O(nlogk) 空间复杂度O(n)=O(n)+O(k)
 6 
 7         //第一步:遍历,且hash存储数字出现次数
 8         int len = nums.length;
 9         Map<Integer,Integer> occuMap = new HashMap<Integer,Integer>();
10         for(int i=0;i<len;i++){
11             occuMap.put(nums[i], occuMap.getOrDefault(nums[i],0)+1);
12         }
13 
14         //第二步:建立小顶堆,每个顶点的元素存储的是一个长度为2的int数组,第一个元素是数字,第二个元素是数字出现的次数
15         PriorityQueue<int[]> queue = new PriorityQueue<int[]>(
16             //里面要记得写对比排序函数,这里的语法结构我之前是完全不知道该怎么写的!!!!!!!
17             new Comparator<int[]>(){
18                 public int compare(int[] m, int[] n){
19                     return m[1]-n[1];
20                 }
21             }
22         );
23 
24         //第三步:遍历hash表,然后更新堆结构;;  这里又有新的语法结构!!!哭了
25         for(Map.Entry<Integer,Integer> entry: occuMap.entrySet()){ //因为key和value都需要,所以用的这个结构
26             int num = entry.getKey(), count = entry.getValue();
27             if(queue.size()==k){//注意这里的语法是size
28                 if(queue.peek()[1]<count){ //取出堆顶
29                     queue.poll(); //删除一个元素
30                     queue.offer(new int[]{num,count}); //插入一个元素,,这里也注意语法结构
31                 }
32             }else{
33                 queue.offer(new int[]{num,count}); //插入一个元素
34             }
35 
36         }
37 
38         //第4步:取出并返回结构
39         int[] ans = new int[k];
40         for(int i=0;i<k;i++){
41             ans[i] = queue.poll()[0];
42         }
43         return ans;
44 
45         
46 
47         //方法二:使用的是快速排序的思路,我没仔细看,有时间复习的时候可以再看
48 
49     }
50 }