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

题目描述

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

 

 

思路：第一种方法是抵消的思路，如果一个数字在一个数组中出现的次数超过一半，那么一一抵消之后，最后剩下的一定是目标数字。一定要注意找到元素之后要验证是否该数字超过数组长度的一半。

维护两个变量，一个记数，一个保存数组元素，如果遍历到下一个数字的时候，和保存数字相同，则记数值加1，否则减1。注意这两个变量初始化，记数值开始为1，进入循环后如果变为0了，要重新赋值为1，并且保存值的变量也更新。

class Solution {
public:
    bool checked(vector<int> &numbers,int num){//检测得到的答案是否合法，查过数组数量的一半
        int len = 0;
        for(int i = 0;i < numbers.size();++i){
            if(num == numbers[i]){
                ++len;
            }
        }
        if(len <= (numbers.size() / 2)){
            return false;
        }
        return true;
    }
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty()){
            return 0;
        }
        int cnt = 1;//先初始化为1
        int flag = numbers[0];
         
        for(int i = 0;i < numbers.size();++i){
            if(cnt == 0){
                cnt  = 1;
                flag = numbers[i];
            }
            else if(flag == numbers[i]){
                ++cnt;
            }
            else{
                --cnt;
            }
        }
         
        if(checked(numbers,flag)){
            return flag;
        }
        return 0;
    }
};

第二种思路是借鉴快速排序的方法，事实上可以不用对数组进行排序，或者说仅部分排序，受快速排序的partition函数的启发，我们可以利用反复调用partition函数来求的该数字。我们现在数组中随机选取一个数字，而后通过Partition函数返回该数字在数组中的索引index，如果index刚好等于n/2，则这个数字便是数组的中位数，也即是要求的数，如果index大于n/2，则中位数肯定在index的左边，在左边继续寻找即可，反之在右边寻找。这样可以只在index的一边寻找，而不用两边都排序，减少了一半排序时间。这种情况的平均时间复杂度大致为：T(n) = n+n/2+n/4+n/8+....+1，很明显当n很大时，T(n)趋近于2n，也就是说平均情况下时间复杂度为O(n),但是这种情况下，最坏的时间复杂度依然为O(n*n)，最坏情况下，index总是位于数组的最左或最右边，这样时间复杂度为T(n) = n+n-1+n-2+n-3+....+1 = n(n-1)/2，显然，时间复杂度为O(n*n)，空间复杂度为O(1)。

idx = partition(numbers,lo,hi);位置非常重要，下面这种在下题就有bug，这题没毛病，不过还是应该idx定义的时候写这个。

class Solution {
public:
    int partition(vector<int> &numbers,int lo,int hi){
        int pos = lo + rand() % (hi - lo + 1);
        int pivot = numbers[pos];
        swap(numbers[lo],numbers[pos]);
        while(lo < hi){
            while(lo < hi){//从右往左找第一个小于pivot
                if(numbers[hi] > pivot){
                    --hi;
                }
                else{
                    numbers[lo] = numbers[hi];
                    ++lo;
                    break;
                }
            }
            
            while(lo < hi){//从左往右找第一个大于pivot
                if(numbers[lo] < pivot){
                    ++lo;
                }
                else{
                    numbers[hi] = numbers[lo];
                    --hi;
                    break;
                }
            }
        }
        numbers[lo] = pivot;
        return lo;
    }
    bool checked(vector<int> &numbers,int flag){
        int len = 0;
        for(int i = 0;i < numbers.size();++i){
            if(numbers[i] == flag){
                ++len;
            }
        }
        if(len <= (numbers.size() / 2)){
            return false;
        }
        return true;
    }
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty()){
            return 0;
        }
        int mid = numbers.size() / 2 ;
        int idx = 0;
        int lo = 0,hi = numbers.size() - 1;
        while(idx != mid){
            idx = partition(numbers,lo,hi);
            if(idx < mid){
                lo = idx + 1;                
            }
            if(idx > mid){
                hi = idx - 1;               
            }
        }
        if(checked(numbers,numbers[idx])){
            return numbers[idx];
        }
        return 0;
    }
};

 正确版本：

class Solution {
public:
    int partition(vector<int> &numbers,int lo,int hi){
        int pos = lo + rand() % (hi - lo + 1);
        int pivot = numbers[pos];
        swap(numbers[lo],numbers[pos]);
        while(lo < hi){
            while(lo < hi){//从右往左找第一个小于pivot
                if(numbers[hi] > pivot){
                    --hi;
                }
                else{
                    numbers[lo] = numbers[hi];
                    ++lo;
                    break;
                }
            }
            
            while(lo < hi){//从左往右找第一个大于pivot
                if(numbers[lo] < pivot){
                    ++lo;
                }
                else{
                    numbers[hi] = numbers[lo];
                    --hi;
                    break;
                }
            }
        }
        numbers[lo] = pivot;
        return lo;
    }
    bool checked(vector<int> &numbers,int flag){
        int len = 0;
        for(int i = 0;i < numbers.size();++i){
            if(numbers[i] == flag){
                ++len;
            }
        }
        if(len <= (numbers.size() / 2)){
            return false;
        }
        return true;
    }
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty()){
            return 0;
        }
        int mid = numbers.size() / 2 ;
        int idx = 0;
        idx = partition(numbers,lo,hi);
        int lo = 0,hi = numbers.size() - 1;
        while(idx != mid){            
            if(idx < mid){
                lo = idx + 1;                
            }
            if(idx > mid){
                hi = idx - 1;               
            }
            idx = partition(numbers,lo,hi);
        }
        if(checked(numbers,numbers[idx])){
            return numbers[idx];
        }
        return 0;
    }
};