剑指offer 面试题29：数组中出现次数超过一半的数字

题目：
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

解法：
假设将数组排序，因为所求数字出现次数超过一半，则arr[n/2]即为所求。
排序的时间复杂度O(nlogn)

既然arr[n/2]即为所求，那实际上用不着排序，找出第n/2大的数字即可。
而在长度为n的数组中，找到第k大的数字有成熟的、基于快排partition的算法。

一遍partition，把大于pivot的统一放到左边，小于pivot的统一放到右边。如果此时pivot刚好等于所求数字，则算法结束。
如果左边的个数小于k，则所求一定在右边，因此对右边递归查找即可。反之则对左边递归查找。

int partition(int *arr, int low, int high) {
    if (arr == 0 || low >= high) return;
    int  pivot = arr[high];
    --high;
    while (low < high) {
        while (low < high && arr[low] >= pivot) ++low;
        while (low < high && arr[high] < pivot) --high;
        if (low != high) {
            swap(arr[low], arr[high]);
        }  
    }
    swap(pivot, arr[low]);
    return low;
}

partition的第二种写法：

int partition(int *arr, int low, int high) {
    if (arr == 0 || low >= high) return;
    int pivot = arr[high];
    int location = low - 1;
    for (int i = low; i < high; ++i) {
        if (arr[i] >= pivot) {
            swap(arr[i], arr[++location]);
        }
    }
    swap(arr[location+1], pivot);
    return location+1;
}

从数组中找到第k大的元素：

int findK(int *arr, int begin, int end, int k) {
    int p = partition(arr, begin, end);
    if (p == k-1) {
        return arr[p];
    } else if (p > k-1) {
        return findK(arr, begin, p-1, k);
    } esle {
        return findK(arr, p+1, end, k);
    }
}