【剑指offer】数组中出现次数超过数组长度一半的数字，C++实现

原创博文，转载请注明出处！

# 题目

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

举例：输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}，由于数字2在数组中出现了5次，超过数组长度一半，因此输出2。

# 思路

解法一：允许修改输入的数组，时间复杂度为O(n)

解法二：不允许修改输入的数组，时间复杂度为O(n)

原理：

　　假设在数组中出现的次数超过数组长度一半的数字位x，x出现的次数比其他所有数字出现的次数的和都要多。设用于存储x的整形变量res，一个用于存储x出现次数的整形变量count。res初始值为number[0]，count初始值为1。当遍历到下一个数组元素时，如果当前元素和res相同，则count+1，否则count-1。如果count=0，则保存下一个数字，并设置count=1.

举例：

　　res初始值为number[0]，即res=1，count=1。遍历整个数组，遍历到number[1]，number[1]≠res，count-1为0。因为count=0，设置res=2，count=1,......

# 代码

class Solution {

public:

    int MoreThanHalfNum_Solution(vector<int> numbers)

    {

        if(numbers.empty())

            return 0;

        else

        {

            int res = numbers[0];

            int cnt = 1;

            for(int i=1;i<numbers.size();++i)

            {

                if(numbers[i]==res)

                    cnt++;

                else

                    cnt--;

                if(cnt==0)

                {

                    res=numbers[i];

                    cnt=1;

                }

            }

            cnt=0;

            for(int i=0;i<numbers.size();++i)

            {

                if(numbers[i]==res)

                    cnt++;

            }

            if(cnt*2>numbers.size())

                return res;

            else

                return 0;

        }

    }

};

巴特西

【剑指offer】数组中出现次数超过数组长度一半的数字，C++实现

# 题目

# 思路

# 代码

最新文章

热门文章