数组中出现次数超过一半的数

题目描述：

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

解题思路：

如果数组中存在一个次数超过一半的数字，那么它在排好序的数组中的下标一定是2/n

所以，我们借用快速排序的思想，每次随机的取数组中的一个数字，将其放置在其所在的下标位置：

1. 若该数字的位置下标小于2/n，则说明下标为2/n的数字在其右侧，继续在其右侧寻找下标等于2/n的数字
2. 若该数字的位置下标大于2/n，则说明下标为2/n的数字在其左侧，继续在其左侧寻找下标等于2/n的数字

直到找到下标位于2/n的数字，并对该数字进行验证，看数组中该数字出现的次数是不是大于2/n

代码：

class Solution{
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if (numbers.empty()) {
            return 0;
        }
        int n = numbers.size();
        // 算出数组中，位于n/2的下标
        // 如果数组的大小为奇数个，则需要下标为size/2的数字
        // 如果数组的大小为偶数个，则需要下标为size/2的数字
        int middle = n >> 1;
        int start = 0, end = n - 1;
        int index = partition(numbers, start, end);
        while (index != middle) {
            // 如果找到的index在middle之前，则需要找数组的后半部分
            if (index < middle) {
                // 更新新的start
                start = index + 1;
                index = partition(numbers, index + 1, end);
            }
            // 如果找到的index在middle之后，则需要找数组的前半部分
            else {
                // 更新新的end
                end = index - 1;
                index = partition(numbers, start, index - 1);
            }
        } // 直到index == middle
        int result = numbers[middle];

        if (!checkMoreThanHalf(result, numbers, n))
            return 0;

        return result;
    }
private:
    int partition(vector<int>& numbers, int start, int end) {
        // 取数组中的第一个元素作为轴点
        int pivot = numbers[start];
        int i = start, j = end;
        while (i < j) {
            // 从后向前遍历，若数字大于pivot，则继续向前推进
            // 反之，将该数字置于现在的空位置
            while (i < j && numbers[j] >= pivot) {
                --j;
            }
            numbers[i++] = numbers[j];

            // 从前向后遍历，若数字小于pivot，则继续向后推进
            // 反之，将该数字置于现在的空位置
            while (i < j && numbers[i] <= pivot) {
                ++i;
            }
            numbers[j--] = numbers[i];
        }
        // 此时退出外层的while循环
        // i == j
        numbers[i] = pivot;
        // 将此下标返回
        return i;
    }

    bool checkMoreThanHalf(int num, vector<int>& numbers, int length) {
        int count = 0;
        for (int i = 0; i < length; ++i) {
            if (num == numbers[i])
                ++count;
        }
        if (count >= ((length >> 1) + 1)) {
            return true;
        }
        else 
            return false;
    }
};

2018.10.23