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

忘是亡心i 2022-05-31 11:09 162阅读 0赞

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

分析：

第一种思路，把序列从小到大排个序，然后相同的数字一定是连续的，记录连续数的个数，判断其长度。时间复杂度为O(nlog(n))，时间主要用在排序上。

参考代码：

class Solution {
    public:
        int MoreThanHalfNum_Solution(vector<int> numbers) {
            int sz = numbers.size();
            if( sz < 1)
                return 0;
            sort(numbers.begin(),numbers.end());
            int num = numbers[0];
            int cnt = 1;
            for( int i = 1; i < sz; i++)
            {
                if( numbers[i] == num)
                    cnt++;
                else
                {
                    if( cnt > sz/2)
                        break;
                    else
                    {
                        num = numbers[i];
                        cnt = 1;
                    }
                }
            }
            if( cnt > sz/2)
                return num;
            else
                return 0;
        }
    };

第二种思路：假设存在出现次数超过原序列长度一般的数字，那么我们可以通过cnt的加减来找到这个num，最后在遍历一遍序列，计算该num出现的次数并加以判断即可。这种方法的时间复杂度为O(n)，比上一种方法简洁。

参考代码：

class Solution {
    public:
        int MoreThanHalfNum_Solution(vector<int> numbers) {
            int sz = numbers.size();
            if( sz < 1)
                return 0;
            int num = numbers[0];
            int cnt = 1;
            for( int i = 1; i < sz; i++)
            {
                if( cnt == 0)
                {
                    num = numbers[i];
                    cnt = 1;
                }
                else if( cnt > 0 && num == numbers[i])//这里cnt>0是必然的，可不用做判断
                    cnt++;
                else
                    cnt--;
            }
            
            cnt = 0;
            for( int i = 0; i < sz; i++)
            {
                if( numbers[i] == num)
                    cnt++;
            }
            if( cnt > sz/2)
                return num;
            else
                return 0;
        }
    };