题目描述

blablabla

样例

blablabla

算法1

基于快排的思想找中位数，如果n/2位置的元素恰好是中位数，则说明该元素出现的次数超过数组长度的一半 $O(n)$

C++ 代码

class Solution {
public:
    int partion(int l, int r, vector<int> &nums){
        if(l>=r) return l; 
        int st = (l+r)/2;
        int c = nums[st];
        nums[st] = nums[l];
        nums[l] = c;
        int index = l;
        l++;
        while(l<r){

            while(nums[r] > c && l<r){
                r--;
            }
            while(nums[l] <= c && l<r){
                l++;
            }
            if (l<r){
                int t = nums[l];
                nums[l] = nums[r];
                nums[r] = t;

            }
        }
        nums[index] = nums[l];
        nums[l] = c;

        return l;
    }
    int moreThanHalfNum_Solution(vector<int>& nums) {
        if (nums.size()==0) return 0;

        int l = 0;
        int r = nums.size()-1;
        int st = r/2;
        int index = partion(l,r,nums);
        while(index != (nums.size()-1)/2 ){
             if (index > (nums.size()-1)/2 ){
                 index = partion(l,index-1,nums);
             }
             else{
                 index = partion(index+1,r,nums);
             }
         }

        return nums[index];
    }
};