題目描述
設計一個找到數(shù)據(jù)流中第K大元素的類（class）。注意是排序后的第K大元素，不是第K個不同的元素。
你的 KthLargest 類需要一個同時接收整數(shù) k 和整數(shù)數(shù)組nums 的構(gòu)造器，它包含數(shù)據(jù)流中的初始元素。每次調(diào)用 KthLargest.add，返回當前數(shù)據(jù)流中第K大的元素。
示例：
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3); // returns 4
kthLargest.add(5); // returns 5
kthLargest.add(10); // returns 5
kthLargest.add(9); // returns 8
kthLargest.add(4); // returns 8
說明：
可以假設 nums 的長度≥ k-1 且k ≥ 1。
解
這道題被打上的標簽是堆的一種數(shù)據(jù)結(jié)構(gòu)，那么就用堆的思路去解決這道題。
堆的性質(zhì)有兩種：
- 左右節(jié)點的元素值不能大于父節(jié)點或者不能小于父節(jié)點的元素值；
- 堆是一種完全二叉樹
先了解堆
1550833872918.png
上面的數(shù)據(jù)結(jié)構(gòu)是一種二叉堆，更多的堆可以是三叉堆甚至d叉堆。。。
- 最小堆：每個父節(jié)點都比左右節(jié)點的元素值要小
- 最大堆：每個父節(jié)點都比左右節(jié)點的元素值要大
移除某個節(jié)點和堆頂一樣的，判斷條件就是左右節(jié)點有沒有比父節(jié)點的元素更小的值。
添加節(jié)點也是一樣的，因為堆是一種完全二叉樹，底層采用數(shù)組的形式，添加節(jié)點加在數(shù)組的末尾，然后和父節(jié)點比較，如果比父節(jié)點小的則交換，直到堆頂。如果沒有比父節(jié)點小的則停止交換。
刪除堆頂.gif
過程
題目要求是找到排序后的第K大個元素值，可以使用只有K長度的最小堆，堆頂?shù)脑刂祫t是最小的。
初始化.gif
添加元素并返回堆頂元素值
kthLargest.add(5)
add添加元素并返回堆頂元素.gif
kthLargest.add(10)
siftdown.gif
最終代碼如下：
class KthLargest {
private int k;
MinHeap<Integer> arr;
public KthLargest(int k, int[] nums) {
this.k = k;
// 只有k長度的最小堆
arr = new MinHeap<>(k);
for (int num : nums) {
add(num);
}
}
public int add(int val) {
arr.heapify(val);
return arr.peek();
}
/**
* 自定義最小堆，底層采用數(shù)組數(shù)據(jù)結(jié)構(gòu)
* E 數(shù)據(jù)類型需要繼承Comparable，具有數(shù)值比較的功能
*/
private class MinHeap<E extends Comparable<E>> {
private Array<E> data;
public MinHeap() {
data = new Array<>();
}
public MinHeap(int capacity) {
data = new Array<>(capacity);
}
/**
* 0
* 1 2
* 3 4 5 6
* 父節(jié)點 i
* 左節(jié)點 2 * i + 1
* 右節(jié)點 2 * i + 2
*
* @param index
* @return 返回index父節(jié)點的索引
*/
private int parent(int index) {
if (index == 0) {
throw new IllegalArgumentException("索引為0沒有父節(jié)點");
}
return (index - 1) / 2;
}
private int leftChild(int index) {
return index * 2 + 1;
}
public void add(E e) {
// 使用數(shù)組數(shù)據(jù)結(jié)構(gòu)添加元素置于末尾
data.add(e);
siftUp(data.getSize() - 1);
}
/**
* 最小堆的性質(zhì)：左右節(jié)點的元素值不能大于父節(jié)點的元素值
*
* @param index 當前索引
*/
private void siftUp(int index) {
// 當前節(jié)點與父結(jié)點進行比較，當前節(jié)點比父節(jié)點小則進行交換
while (index > 0 && data.get(parent(index)).compareTo(data.get(index)) > 0) {
data.swap(index, parent(index));
index = parent(index);
}
}
/**
* 這里和Java中的PriorityQueue類 heapify 方法實現(xiàn)同樣的效果
* ★★★★★
* 根據(jù)題意
* 如果待比較的元素比最小堆堆頂大，則替換
*
* @param e 待比較的元素值
*/
public void heapify(E e) {
if (peek() == null) {
data.add(e);
return;
} else if (data.getSize() < k) {
data.add(e);
siftUp(data.getSize() - 1);
} else if (peek().compareTo(e) < 0) {
data.set(e);
// 從堆頂開始
siftDown(0);
}
}
/**
* @param index
*/
private void siftDown(int index) {
// while循環(huán)，依據(jù)條件是是否存在左孩子
while (leftChild(index) < data.getSize()) {
int j = leftChild(index);
// 尋找左右孩子的最小的元素值
if (j + 1 < data.getSize() && data.get(j).compareTo(data.get(j + 1)) > 0) {
// 存在右孩子而且右孩子的元素值比左孩子的元素值更小
j++;
}
if (data.get(index).compareTo(data.get(j)) < 0) {
break;
}
// 運行到此處說明存在左右孩子的元素值比父節(jié)點更小
data.swap(index, j);
index = j;
}
}
/**
* @return 返回頂節(jié)點
*/
public E peek() {
if (data.getSize() == 0) {
return null;
}
return data.get(0);
}
public int getSize() {
return data.getSize();
}
public boolean isEmpty() {
// return getSize() == 0 ? true: false;
return data.isEmpty();
}
}
/**
* 自定義數(shù)組，數(shù)據(jù)類型為E
*/
private class Array<E> {
private E[] data;
private int size;
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
public Array() {
// 數(shù)組長度默認為10
this(10);
}
/**
* @param index 當前索引
* @return 返回元素值
*/
public E get(int index) {
if (index < 0 || index > size - 1) {
throw new IllegalArgumentException("數(shù)組越界");
}
return data[index];
}
public void set(E e) {
set(0, e);
}
public void set(int index, E e) {
data[index] = e;
}
/**
* 添加元素
*
* @param index 索引
* @param e 元素值
*/
public void add(int index, E e) {
// 為什么index > size 而不是 index > size - 1
// 是因為在末位添加數(shù)據(jù)的時候剛好是在size上面，所以index最大為size
if (index < 0 || index > size) {
throw new IllegalArgumentException("index索引不在數(shù)組范圍內(nèi)");
}
// 擴容
if (size == data.length) {
resize(2 * data.length);
}
// 將index索引后面的數(shù)值往后移一位
for (int i = size; i > index; i--) {
data[i] = data[i - 1];
}
data[index] = e;
size++;
}
/**
* 末尾添加元素
*
* @param e 元素值
*/
public void add(E e) {
add(size, e);
}
/**
* 刪除元素
*
* @param index 索引
* @return 返回被刪除的元素
*/
public E remove(int index) {
if (index < 0 || index > size - 1) {
throw new IllegalArgumentException("index索引不在數(shù)組范圍內(nèi)");
}
E ret = data[index];
// index索引后的元素往前移動一位
for (int i = index; i < size - 1; i++) {
data[index] = data[index + 1];
}
size--;
data[size - 1] = null;
// 縮容，而且數(shù)組為1的時候就不能再除2 ，1/2 = 0，長度為0 的數(shù)組就不能擴容
if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return ret;
}
/**
* 輸出末尾元素
*
* @return 返回被刪除的元素
*/
public E remove() {
return remove(size - 1);
}
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
/**
* @return 返回數(shù)組的長度
*/
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0 ? true : false;
}
public void swap(int index1, int index2) {
E tmp = data[index1];
data[index1] = data[index2];
data[index2] = tmp;
}
}
}
