LeetCode之 数组中的第K个最大元素

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

---

题解

1. 这道题有多种解法，一个很容易想到的算法为 降序排序整个数组 然后取索引为K-1的元素 即可。
2. 当我们用冒泡排序等初等排序时，这道题的 时间复杂度为O( N 2 N_2 N2​)。
3. 以冒泡排序为例，其实当我们进行了K趟排序之后，就已经找到了第K个最大元素，已经没有必要进行剩下的排序，这时时间复杂度可以降到 O(N*K)。
   今天讲一个较为巧妙的方法，最小堆 来解决这个问题。整个过程可以从下图中看到。

我们维护一个大小为k+1的小顶堆，当堆得数量大于等于K+1时，Pop出堆顶元素，当整个数组遍历完之后，堆顶元素就是我们要找得第K大元素。

---

详细代码

• 这里也给出如何建立一个小顶堆的过程。
• 我们用数组来实现，某一索引 Index的父节点可以用 Parent = (Index-1)/2 来表示。
• 某一索引 Index的左子节点可以用 LeftChild = (Index*2)+1 表示，右子节点可以用 LeftChild+1 表示。

public class Solution
{
    private int[] minHeap;
    private int curHeapSize;

    public int FindKthLargest(int[] nums, int k)
    {
        minHeap = new int[k + 1];
        curHeapSize = 0;

        for (int i = 0; i < nums.Length; i++)
        {
            int curValue = nums[i];
            Push(curValue);
            if (Size() >= k + 1)
            {
                Pop();
            }
        }

        return Peek();
    }

    private void Push(int value)
    {
        int curIndex = curHeapSize, nextIndex = 0;
        // 首先将元素放到数组的末端，然后自底向上进行检测替换
        minHeap[curHeapSize++] = value;
        while (curIndex > 0)
        {
            nextIndex = (curIndex - 1) / 2;
            if (minHeap[curIndex] >= minHeap[nextIndex]) break;
            Swap(ref minHeap[curIndex], ref minHeap[nextIndex]);
            curIndex = nextIndex;
        }
    }

    private int Pop()
    {
    	// 首先将堆顶元素暂存，然后用数组末端的值替换堆顶元素后，自顶向下进行检测替换
        int tempValue = minHeap[0];
        int curIndex = 0, nextIndex = 0;
        minHeap[0] = minHeap[--curHeapSize];

        while (curIndex * 2 + 1 <= curHeapSize)
        {
            nextIndex = curIndex * 2 + 1;
            if (nextIndex + 1 <= curHeapSize && minHeap[nextIndex + 1] < minHeap[nextIndex]) nextIndex++;
            if (minHeap[curIndex] <= minHeap[nextIndex])
            {
                return tempValue;
            }

            Swap(ref minHeap[curIndex], ref minHeap[nextIndex]);
            curIndex = nextIndex;
        }

        return tempValue;
    }

    private int Peek()
    {
        return minHeap[0];
    }

    private int Size()
    {
        return curHeapSize;
    }

    private void Swap(ref int a, ref int b)
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }
}