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

时间:2021-01-04 11:06:58

题目描述

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
开始的思路:思路很简单,申请一个map。将所有元素作为下标,value值为出现的次数。
代码如下:
int MoreThanHalfNum_Solution(vector<int> numbers) {
        int length = numbers.size();
        if(length == 1) return numbers[0];
        map<int,int> m;
        for(int i = 0; i < length; i++)
        {
            m[numbers[i]] += 1; 
        }
        int len = m.size();
        for(int i  = 0; i < len; i++)
        {
            if(m[i] > length/2)
                return i;
        }
        return 0;
    }

但是map浪费空间和时间。

思路二:我们要找的数字出现的次数超过一半,所以它比其他变量加起来都多。设两个变量,一个记录数字,一个记录次数,遍历数组,当前数字不等于记录的数字,则次数--,如果当前数字==记录的数字,则次数++。如果有满足条件的数字,即为变量的数字。需要注意的是最后的得到的数字,要进行验证。

只有当有数字出现一半时,计数为零。所以不能通过此条件判断是否有符合条件的值。如果没有符合条件的点,那么变量记录的为最后一个值。

例如样例:1 2 3 2 4 2 5 2 3  没有符合的数字,则最后num存的为3

代码:

int MoreThanHalfNum_Solution(vector<int> numbers) {
        int length = numbers.size();
        int nCount = 1;
        int num = numbers[0];
        for(int i = 1; i < length; i++)
        {
            if(nCount == 0)
            {
                num = numbers[i] ;
                nCount++;
            }
            else if(numbers[i] == num)
            {
                nCount++;
            }
            else
            {
                nCount--;
            }
        }
        nCount = 0;
        for(int i = 0 ; i < length;i++)
        {
            if(numbers[i] == num)
                nCount++;
        }
        if(nCount > length/2)
            return num;
        else
            return 0;
    }

思路三:数组排序后,如果符合条件的数存在,则一定是数组中间那个数。(比如:1,2,2,2,3;或2,2,2,3,4;或2,3,4,4,4等等)

这种方法虽然容易理解,但由于涉及到快排sort,其时间复杂度为O(NlogN)并非最优;

参考代码:

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers)
    {
        // 因为用到了sort,时间复杂度O(NlogN),并非最优
        if(numbers.empty()) return 0;
         
        sort(numbers.begin(),numbers.end()); // 排序,取数组中间那个数
        int middle = numbers[numbers.size()/2];
         
        int count=0; // 出现次数
        for(int i=0;i<numbers.size();++i)
        {
            if(numbers[i]==middle) ++count;
        }
         
        return (count>numbers.size()/2) ? middle :  0;
    }
};