kth-largest-element-in-an-array.md · carloz/leetcode

### 算法：Heap 堆

### 题目

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

```shell
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（堆）来实现

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

![](https://images2018.cnblogs.com/blog/1297600/201802/1297600-20180225121948371-554379317.png)

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

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

### Java解法

```java
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解法

```python

```

carloz/leetcode

简介

发行版

贡献者

近期动态

carloz/leetcode .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

carloz/leetcode