# 数组中的第 K 个最大元素

给定整数数组 nums 和整数 k ，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

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

示例 2:

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

提示：

# 使用小顶堆来解决问题

比如说如下案例：

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

找第 2 大的元素，我们就把前两个元素先加入到小顶堆，如果 k = 4 那么我们就把前面 4 个元素加入到小顶堆，我们先看前两个的

后续的元素我们不直接添加，而是进行判断如果要添加的元素比堆顶元素小那么什么事儿也不做，如果比堆顶元素大那么就采用 replace 替换掉堆顶元素，然后重新调整小顶堆

我们添加 1 的时候什么也不做当我们添加 5 的时候先 replace 然后调整小顶堆就成了如下图所示：

看到这里差不多就明白了其实队里留的就是 2 个最大的元素

下次 6 的时候它比堆顶元素 3 大，那么就 replace 然后调整小顶堆，此时就如下图所示：

剩下一个 4 没有 5 大那么直接什么也不做

最终经过上述的算法运算后我们小堆顶中就剩下了两个最大的元素那么这两个最大的元素里谁是第二大的呢？

堆顶元素就是第二大的，所以最终我们只要返回堆顶元素就可以了

实现小顶堆类

	/**
	* @author Dkx
	* @version 1.0
	* @2024/1/2217:05
	* @function
	* @comment
	*/
	public class MinHeap
	{
	public int array[];
	public int size;

	public MinHeap(int capacity)
	{
	this.array = new int[capacity];
	}

	public boolean offer(int t)
	{
	// 判断堆是否满了
	if(isFull())
	return false;
	// 调用 up 方法重新调整小顶堆的特性
	up(t, size);
	// 元素个数自增
	size++;
	return true;
	}

	public void up(int offered, int index)
	{
	// 获取当前 index 索引位置
	int child = index;
	while(child > 0)
	{
	// 根据当前 child 位置通过公式获取它的父节点位置
	int parent = (child - 1) / 2;
	// 判断传入的元素值是否小于 parent 索引位置的值
	if(offered < array[parent])
	// 如果小那么就将父节点的值向下移动
	array[child] = array[parent];
	else
	// 如果传入的值大于父节点的值那么就不需要操作直接跳出循环
	break;
	// 将 child 的索引赋值为父节点的索引值
	child = parent;
	}
	// 将当前 child 的索引位置赋值为传入的值
	array[child] = offered;
	}

	public void replace(int replaced)
	{
	array[0] = replaced;
	down(0);
	}

	public int peek()
	{
	return array[0];
	}

	public void swap(int i, int j)
	{
	int t = array[i];
	array[i] = array[j];
	array[j] = t;
	}

	public void down(int parent)
	{
	int left = parent * 2 + 1;
	int right = left + 1;
	int min = parent;
	if(left < size && array[min] > array[left])
	min = left;
	if(right < size && array[min] > array[right])
	min = right;
	if(min != parent)
	{
	swap(min, parent);
	down(min);
	}
	}

	public boolean isFull()
	{
	return size == array.length;
	}
	}

解决题目问题类

打印结果：