数组中第K大元素（java多种方式实现）

向右看齐 2022-01-05 06:51 143阅读 0赞

## 题目描述： ##

Leetcode215题：在未排序的数组中找到第 **k** 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

**示例 1:**

输入: [3,2,1,5,6,4] 和 k = 2输出: 5

**示例 2:**

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4输出: 4

注意题目中并没有声明数组是没有重复数字的，所以要考虑重复数字出现的情况。

在Leetcode评论及题解中吸取大佬的精化，在此一一实现：

### 1. 冒泡排序 ###

最容易想到的方法，从前往后冒，冒k次，在输入数据较大的情况下会超时，适合k较小，数组较有序的排序。

public int findKthLargest(int[] nums, int k) {
    
            int s = 0;
            for(int i=0; i<nums.length-1; i++){
                for(int j=i+1; j<nums.length; j++){
                    if(nums[i] > nums[j]){
                        int tmp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = tmp;
                    }
                }
                if(s++ >= k) break;
            }
            
    
            return nums[nums.length-k];
        }

### 2. 桶排序： ###

先找到数组中的最大最小值，然后创建bucket数组，数组大小为max-min+1；遍历nums数组，以nums\[i\]-min作为bucket索引，该值出现次数为bucket数组值。从后往前遍历bucket数组，设置计数器counts，每次counts+bucket\[j\] ,当counts>=k时，输出j+min, 即是要找的第k个最大的数组的值。

public int findKthLargest(int[] nums, int k) {
           int max = Integer.MIN_VALUE;
           int min = Integer.MAX_VALUE;
           for(int num : nums){
               max = Math.max(max, num);
               min = Math.min(min, num);
           }
            int[] bucket = new int[max-min+1];
           for(int i=0; i<nums.length; i++){
               bucket[nums[i] - min]++;
           }
            int count = 0; 
            for(int j=bucket.length-1; j>=0; j--){                       
                count += bucket[j];
                if(count >= k) return j+min;
            }
            
            return -1;
    }

![20190623161841721.png][]

效率还是蛮高哈~

### 3. 堆排序 ###

先从数组中去k个元素构造k大小的小顶堆，遍历余下的数组值，依次与对顶元素比较，若大于堆顶元素，则删除堆顶元素，将新元素放入，重新建立新的小顶堆。遍历完数组，则最后的堆顶元素即是我们要找的第k个最大元素了。

大、小顶堆是完全二叉树，可用数组实现。首先，实现一个小顶堆：

public class minHeap{
            private int[] data;  //构造小顶堆的数组；
    
            /*
            *构造函数；
            */
            public minHeap(int[] data){
                this.data = data;
                buildMinHeap();
            }
    
            /*
            *构造小顶堆,大小为k；
            */
            private void buildMinHeap(){
                for (int i = (data.length) / 2 - 1; i >= 0; i--) {
            	// 对有孩子结点的元素heapify
                    heapify(i);
                }       
            }
    
            /**
             * 从当前节点开始堆化
             */
            private void heapify(int i) {
                int left = ((i + 1) << 1) - 1;
                int right = ((i + 1) << 1);
                int min = i;
                if(left < data.length && data[left] < data[i]) min = left;
                if(right < data.length && data[right] < data[min]) min = right;
                if(min == i) return;        
                swap(i, min);
                heapify(min);
            }
    
            /*
            *判断当前数，若其大于堆顶元素，取出堆顶，将该数放入堆顶并重新堆化；否则不改变原堆
            */
            private void setRoot(int num){
                if(num <= data[0]) return;
                data[0] = num;
                //重新堆化；
                heapify(0);
            }
    
            private void swap(int i, int j) {
                int tmp = data[i];
                data[i] = data[j];
                data[j] = tmp;
            }
        }

实现查找前k大元素：

public int findKthLargest(int[] nums, int k) {
            // 先取K个元素放入数组topk中
    		int[] topk = new int[k]; 
    		for(int i=0; i<k; i++){
    			topk[i] = nums[i];
    		}
            
            minHeap heap = new minHeap(topk);
            
            for(int i=k; i<nums.length; i++){
                heap.setRoot(nums[i]);
            }
            return topk[0];
        }

小顶堆的方式实现，效率较高。

![20190623113641550.png][]

java中的**PriorityQueue**即是二叉小顶堆来实现的，自己实现一个小顶堆太麻烦，可以借用java的PriortyQueue来实现：

public int findKthLargest(int[] nums, int k) {
           Queue<Integer> queue = new PriorityQueue<>();
           for(int num : nums){ 
               queue.add(num);
               //当queue的大小大于k，每次弹出堆顶的最小元素；
               if(queue.size() > k) queue.poll();           
           }
           return queue.peek();
    }

### ![20190623164142459.png][] ###

### 4. 快速排序 ###

快速排序每次至少能将一个数字放在其排序后的位置，其左边的数据是小于该数字的，右边数据是大于该数字的。判断如果该数据的索引小于最终索引kk(nums.length - k)，则要找的数载该数右侧，则从该数右侧开始继续排序；若索引大于kk, 则要找的数在该数左侧，则从该数左侧开始继续排序；若索引=k-1，则该数字就是要找的数字。

不过快排在基本有序的情况下效率很低，其效率与选择的pivot节点有关。此处我们直接选择排序的第一个数字作为基准piviot。

class Solution {
        
        static int kk; // 第k大元素的快排后索引位置；
        
        public int findKthLargest(int[] nums, int k) {
            kk = nums.length - k; 
            quickSort(nums, 0, nums.length-1);     
            return nums[kk];
        }
        
        private void quickSort(int[] data, int start, int end){
            if(start < end){
                int mid = partition(data, start,end);
                //当第k大位置的数字归位时，结束递归遍历；
                if(mid == kk) return;
                else if(mid > kk) quickSort(data, start, mid-1); 
                else quickSort(data, mid+1, end);
                
            }
        }
        
        private int partition(int[] data, int start, int end ){
            int key = data[start];
            if(start > end) return -1;
            while(start < end){
                //一定要从后往前遍历！
                while(start < end && data[end] >= key) end--;
                if(start < end) swap(data, start, end);
                while(start < end && data[start] <= key) start++;
                if(start < end) swap(data, start, end);            
            }
            
            return start;
        }
        
        private void swap(int[] data, int i, int j){
            int tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }
    }

![2019062316171380.png][]

在此处快排效率一般，综上，该问题最好使用桶排序或小顶堆来实现。

再次记录总结，一起学习，交流。

[20190623161841721.png]: /images/20211229/0f296a8ad0f840eb859612043ab39dee.png
[20190623113641550.png]: /images/20211229/a2ed5659d8154b2e8ee87ee8abbd1bbe.png
[20190623164142459.png]: /images/20211229/933e1f177b85486bb061c6651ea976c2.png
[2019062316171380.png]: /images/20211229/8aaadaff26084642b42046f80d5213ab.png