剑指offer 数组中出现次数超过一半的数字

题目描述

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

代码一、用map

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        map<int,int>m;
        int len=numbers.size();
        for(auto x:numbers){
            m[x]++;
            if(m[x]>len/2)return x;
        }
        return 0;
    }
};

代码二、根据题意可知，经过排序以后该元素一定在数组中间位置，所以可一利用快速排序找中间元素。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int len=numbers.size();
        return quicksort(numbers,0,len-1,len/2);
    }
    int quicksort(vector<int>a,int l,int r,int k){
        int temp=a[l];
        int i=l,j=r;
        while(i<j){
            while(i<j&&a[j]>temp)j--;
            a[i]=a[j];
            while(i<j&&a[i]<temp)i++;
            a[j]=a[i];
        }
        a[i]=temp;
        if(k==i)return a[i];
        else if(i<k)return quicksort(a,i+1,r,k);
        else return quicksort(a,l,i-1,k);
    }
};