Kth Largest Element in an Array

发表于

算法：Heap 堆

题目

url:https://leetcode.com/problems/kth-largest-element-in-an-array/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

分析

用数据结构 Head（堆）来实现

堆：完全二叉树，常常用数组表示

用数组表示一棵树时，如果数组中节点的索引位x，则
a、它的父节点的下标是：(x-1)/2；
b、它的左子节点的下标为：2x + 1；
c、它的右子节点的下标是：2x + 2；

堆的数组实现：https://www.cnblogs.com/g177w/p/8469399.html

Java解法

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
class Solution {
    class Node {
        private int data;
        public Node(int d) {
            this.data = d;
        }
        public int getValue() {
            return this.data;
        }
        public void setValue(int d) {
            this.data = d;
        }
    }
    class Head {
        private Node[] headArray;
        private int maxSize;
        private int currentSize;
        public Head(int maxSize) {
            this.maxSize = maxSize;
            currentSize = 0;
            headArray = new Node[maxSize];
        }
        public boolean isEmpty() {
            return 0 == currentSize;
        }
        public boolean insert(int d) {
            if (this.currentSize == this.maxSize) {
                return false;
            }
            Node node = new Node(d);
            headArray[currentSize] = node;
            trickleUp(currentSize++);
            return true;
        }
        public void trickleUp(int index) {
            int parentIndex = (index - 1) / 2;
            Node node = headArray[index];
            while (index > 0 && 
                   headArray[parentIndex].getValue() < node.getValue()) {
                headArray[index] = headArray[parentIndex];
                index = parentIndex;
                parentIndex = (index - 1) / 2;
            }
            headArray[index] = node;
        }
        public Node remove() {
            Node root = headArray[0];
            headArray[0] = headArray[--currentSize];
            trickleDown(0);
            return root;
        }
        public void trickleDown(int index) {
            int largeChild;
            Node node = headArray[index];
            while (index < currentSize/2) {
                int leftChild = 2 * index + 1;
                int rightChild = 2 * index +2;
                if (rightChild < currentSize && headArray[leftChild].getValue()
                    < headArray[rightChild].getValue()) {
                    largeChild = rightChild;
                } else {
                    largeChild = leftChild;
                }
                if (node.getValue() >= headArray[largeChild].getValue()) {
                    break;
                }
                headArray[index] = headArray[largeChild];
                index = largeChild;
            }
            headArray[index] = node;
        }
        public boolean change(int index, int newValue) {
            if (index < 0 || index > currentSize) {
                return false;
            }
            int oldValue = headArray[index].getValue();
            headArray[index].setValue(newValue);
            if (oldValue < newValue) {
                trickleUp(index);
            } else  {
                trickleDown(index);
            }
            return true;
        }
        public void displayHead() {
             System.out.print("headArray:");
             for (int i = 0; i < currentSize; i++) {
                 if (headArray[i] != null)
                     System.out.print(headArray[i].getValue()+"  ");
                 else
                     System.out.print("--");
             }
             System.out.println("");
             int nBlanks = 32;
             int itemsPerrow = 1;
             int column = 0;
             int j = 0;
             String dots = "........................";
             System.out.println(dots + dots);
             while (currentSize > 0){
                 if (column == 0)
                     for (int i = 0; i < nBlanks; i++) {
                         System.out.print(" ");
                     }
                 System.out.print(headArray[j].getValue());
                 if (++ j == currentSize)
                     break;
                 if (++ column == itemsPerrow){
                     nBlanks /= 2;
                     itemsPerrow *= 2;
                     column = 0;
                     System.out.println();
                 }
                 else
                     for (int i = 0; i < nBlanks * 2 - 2; i++) 
                         System.out.print(' ');
             }
             System.out.println("\n"+dots + dots);
        }
    }
    
    public int findKthLargest(int[] nums, int k) {
        Head head = new Solution().new Head(nums.length);
        for (int x : nums) {
            head.insert(x);
        }
        for (int i=0; i<k-1; ++i) {
            head.remove();
        }
        int ret = head.remove().getValue();
        return ret;
    }
}

Python解法

1
2