By

Contents
  1. 1. 题目
  2. 2. 思路1
  3. 3. 思路2

题目

在未排序的数组中找到第 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
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

思路1

插入一个k大小的最小堆，
满了之后，再最小值比较，然后从上到下堆化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
    public int findKthLargest(int[] nums, int k) {
        Heap heap = new Heap(k);
        for(int i = 0; i< nums.length ; i++){
            heap.insert(nums[i]);
        }
        return heap.maxK();
    }
    static class Heap{
        int[] nums;
        int count;
        int capacity;
        public Heap(int capacity){
            this.nums = new int[capacity+1];
            this.count = 0;
            this.capacity = capacity;
        }
        
        public void insert(int num){
            if( count < capacity){
                notFullInsert(num);
            }else{
                fullInsert(num);
            }
        }
        public void fullInsert(int num){
            int min = nums[1];
            if(num < min){
                return;
            }
            nums[1] = num;
            int minPos = 1;
            int i = 1;
            while(true){
                if(i*2 <= capacity && nums[i] > nums[i*2]){minPos = i*2;}           
                if(i*2+1 <= capacity && nums[minPos] > nums[i*2+1]){minPos = i*2+1;}
                if(i== minPos)break;
                swap(nums,i,minPos);
                i = minPos;
            }
            
        }
        public void notFullInsert(int num){
            int index = count+1;
            nums[index] = num;
            count++;
            while(index/2 > 0 && nums[index/2] > nums[index]){
                swap(nums,index , index/2);
                index = index/2;
            }
        }
        public void swap(int[] array, int fromIndex ,int toIndex){
            int tmp = array[toIndex];
            array[toIndex] = array[fromIndex];
            array[fromIndex] = tmp;
        }
        public int maxK(){
            return nums[1];
        }
    }
}

思路2

先填充 k个大小的数组，然后从下到上进行堆化，
满了之后，再最小值比较，然后从上到下堆化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int[] arrays = new int[k+1];
        
        for(int i = 1 ; i<= k ; i++ ){
            arrays[i] = nums[i-1];
        }
        initTree(arrays);
        
        for(int i = k ; i< nums.length ; i++){
            int min = arrays[1];
            if(min < nums[i]){ 
                arrays[1] = nums[i];
                heapify(arrays,1, k);
                
            }
        }
        return arrays[1];
    }
    private void initTree(int[] array){
        for(int i = array.length/2; i>= 1;i--){
            heapify(array, i, array.length -1);
        }
    }
    private void heapify(int[] array,int i, int n){
        while(true){
            int minPos = i;
            if(i*2 <= n && array[i] > array[i*2]){ 
                minPos = i*2;
            }
            if(i*2+1 <= n && array[minPos] > array[i*2+1]){minPos = i*2+1;}
            if(minPos == i)break;
            swap(array, i, minPos);
            i = minPos;
        }
    }
  
    public void swap(int[] nums , int fromIndex , int toIndex){
        int tmp = nums[toIndex];
        nums[toIndex] = nums[fromIndex];
        nums[fromIndex] = tmp;
    }
Contents
  1. 1. 题目
  2. 2. 思路1
  3. 3. 思路2