找出数组中第k大的数（时间复杂度分析、C++代码实现）. TopK in array. ( leetcode - 215 )

找出数组中第k大的数. TopK in array. ( leetcode - 215 )

最近面试过程中遇到的一个题目，也是大数据时代常见的题目，就来总结一下。

面试题目：

1、10亿数中，找出最大的100个数。用你能想到的最优的时间和空间效率。
2、写出来之后，问时间空间复杂度是多少？如何计算？

LeetCode 215：

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.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

解题思路：

既然要求了时间空间复杂度，就先不考虑对所有数就行排序的方法了（虽然可行，但是效率肯定达不到面试官要求）。

思路：  
1.维护一个k大小的有序序列，然后遍历剩余数据，依次和有序序列中的数比较;
2.如果比有序序列中的最小值大，则将最小值换出;
3.重新对序列排序，直至遍历完所有数据。

Solution 1: 使用最大堆

Using Max-Heap.
时间、空间复杂度分析。
1) 建堆 Build Heap.
    Time O(K) about, SpaceO(K)
        高度 Height: 1-h, h = log(n+1);
        总节点数 Total-Node-Number: 1-n, n = 2^n - 1;
        层数 Layer-Number: 1-i
        每层节点数 Node-Number-per-Layer: 2^(i-1)
        最坏情况，
            倒数第一层节点需要向下比较 0 次，
            倒数第二层节点需要向下比较 1 次，
            倒数第三层节点需要向下比较 2 次，
            ...
            (每次只需要比较 与根节点交换的 分支即可)
        Time(h) = 2^(h) * 0 + 2^(h-1) * 1 + 2^(h-2) * 2 + ... + 2^1 * (h-1)
        错位相减法：
        等式两边同乘以 2，得：
        2*Time(h) = 2^(h+1) * 0 + 2^(h) * 1 + 2^(h-1) * 2 + ... + 2^2 * (h-1)
        Time(h) = 2*Time(h) - Time(h)
                = 2^(h) * 1 + 2^(h-1) + 2^(h-2) + ... + 2^2 - 2^1(h-1)
                = { 2^h + 2^(h-1) + 2^(h-2) + ... + 2^2 } - 2(h-1)
                = { (4 - 2^(h+1) ) / (1-2) } - 2h +2         // 大括号{}内是等比数列求和公式.
                = {2^(h+1) - 4} - 2h + 2
                = 2^(h+1) - 2h - 2
        lim{Time(h)} = lim{n - 2log(n) - 2}  = n             // h = log(n+1), n 足够大时，求极限.
    所以，建堆的时间复杂度大约为 Time O(n).

2) 调整单个节点 Heapify.
    Time O(logN)
        每次调整只需选择当前节点的一个分支，因此调整节点的时间复杂度 O(logN).

3）调整堆
    Time O(nlogn)
即： 堆排序heap_sort时，交换堆顶元素和堆尾元素后，重新调整堆，对n/2元素都进行一次调整，因此 Time O(nlogn).

class SolutionHeap{

public:

    int findKthLargest(vector<int> &nums, int k)
    {
        int size = nums.size();
        int index = 0;
        vector<int> k_size_array;
        k = k < size ? k : size;

        // 前 k 个元素入堆.
        for (index = 0; index < k; index ++)
        {
            k_size_array.push_back(nums[index]);
        }

        // 建 size = k 大小的小根堆.
        buildMinHeapify(k_size_array);

        // 其余元素依次和堆顶元素（最大值中的最小值）比较
        // 如果大于堆顶元素，则交换，重新调整堆(从根节点调整依次即可)。
        for (; index < size; index++)
        {
            if (k_size_array[0] < nums[index])
            {
                swap(k_size_array[0], nums[index]);
                minHeapify(k_size_array, 0);
                //print_array(k_size_array);
            }

        }

        // 堆顶元素即第k大元素，return.
        return k_size_array[0];
    }

    void print_array(vector<int> &nums)
    {
        vector<int>::iterator iter;
        for (iter = nums.begin(); iter != nums.end(); iter++)
        {
            cout << *iter << endl;
        }
        cout << endl;
    }

private:

    inline int leftChild(int index)
    {
        return ((index << 1) + 1);
    }

    inline int rightChild(int index)
    {
        return ((index << 1) + 2);
    }

    inline int parent(int index)
    {
        return ((index - 1) >> 1);
    }

    // 调整堆
    void minHeapify(vector<int> &array, int index)
    {
        int length = array.size();
        int left = leftChild(index);
        int right = rightChild(index);

        int least = index;
        if (left < length && array[index] > array[left])     // 切记先判断下标是否越界
        {
            least = left;
        }
        if (right < length && array[least] > array[right])   // 切记先判断下标是否越界
        {
            least = right;
        }

        if (least != index)
        {
            swap(array[least], array[index]);
            minHeapify(array, least);
        }
    }

    // 建小根堆
    void buildMinHeapify(vector<int> &array)
    {
        int index = parent(array.size() - 1);

        for (; index >= 0; index--)
        {
            minHeapify(array, index);
        }
    }
}; 

Solution 2：优先级队列

具体代码见：https://github.com/Jackson-Y/Machine-Learning/blob/master/algorithms/top_k_in_array.cpp

Solution 3：multiset

具体代码见：https://github.com/Jackson-Y/Machine-Learning/blob/master/algorithms/top_k_in_array.cpp

Solution 4：Partition（idea from quick-sort）

具体代码见：https://github.com/Jackson-Y/Machine-Learning/blob/master/algorithms/top_k_in_array.cpp