7月23日：数组中第K大个元素

题目如下：

这个题目还是算比较经典的吧，可能笔试的时候出现的不多，但是面试的时候问的可能会比较多。面试官虽然不会直接问数组中的第K个元素，但是他可能会问到：如果我手上有100w个数，我现在要快速找出第3大的数，如何最快实现呢？，通常我们首先能想到的是先对那100w个数进行排序，然后按照排序结果取第几个元素就可以了，所以这道题的重点是如何选取排序算法。

一般对于这种找出最大或者最小的元素的问题，一般都是用堆排序算法来解决的，次之是快速排序。

那么为什么使用堆排序对于这道题会更好呢？因为堆排序每次都是选出最大最大或者最小值作为堆顶元素，然后再次构建最大堆或者最小堆，再选出第二大或者第二小的元素，这样的话我们就不用完全将数组排好序就可以找到第几大或者第几小的元素了，这样就节省了时间。

本菜鸟第一个想到的虽然是堆排序，但是堆排序中的堆的构建，堆的排序还是不是很熟，所以做题的时候选择了用java中的库函数来先进行排序，然后再选取最大的第K个元素。

但是如果在面试中如果被问到这个问题，然后让写代码的话，你这样写基本就会被挂掉。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        buildMaxHeap(nums, heapSize);
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }

    public void buildMaxHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    public void maxHeapify(int[] a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a, i, largest);
            maxHeapify(a, largest, heapSize);
        }
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}