题解 | #数组中出现次数超过一半的数字#

思路

参考《剑指offer》
1、一个数字出现次数超过一半，那么排序后的中间位置的元素肯定就是这个要求的数字
2、借助Partition函数，返回一个索引index，代表该位置的元素在排序后的数组中下标是index，比arr[index]小的都在左侧，比arr[index]大的都在右侧；
3、根据index和middle的大小关系，更新start、end区间，继续Partition，直到index==middle

代码

class Solution {
public:

    int Partition(vector<int>& arr, int L, int R){
        int left = L;
        int right = R;
        int key = arr[left];
        while(left<right){
            while(left < right && arr[right]>=key){
                right--;
            }
            arr[left] = arr[right];

            while(left < right && arr[left]<=key){
                left++;
            }
            arr[right] = arr[left];


        }

        arr[left] = key;
        return left;
    }
    int MoreThanHalfNum_Solution(vector<int> numbers) {

        /*
        // 脑残做法
        std::unordered_map<int, int> map_of_times;
        for(const auto& ele:numbers)
        {
            map_of_times[ele]++;
        }
        for(const auto& pair_:map_of_times){
            if(pair_.second>numbers.size()/2){
                return pair_.first;
            }
        }
        return 0;
        */

        // 快排的思想
        // 出现次数超过一半，那么最后排序好的数组中间的元素一定是这个数字，所以可以多次使用Partition函数，直到其返回的索引是mid为止
        int middle = (0+numbers.size()-1)/2;
        int start = 0;
        int end = numbers.size()-1;
        int index = Partition(numbers, 0, numbers.size()-1);
        while(middle!=index){
            if(index>middle){
                end = index-1;
                index = Partition(numbers, start, end);
            }

            else{
                start = index+1;
                index = Partition(numbers, start, end);
            }
        }

        return numbers[index];

    }
};