一组无序的整数找出出现次数大于一半的数字

45 阅读 0 评论 30 点赞

我是靠谱客的博主勤恳长颈鹿，最近开发中收集的这篇文章主要介绍一组无序的整数找出出现次数大于一半的数字，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在看一个讲算法的视频公开课里看到了这个题目，当时脑子里想到的第一个算法就是先排序然后进行遍历，具体的做法就是先将这组整数快速排序，然后在进行遍历，总的时间复杂度就是O(nlgn)，但是实际上这并不是最优算法解，但是无奈自己的算法太渣了，而且是才接触算法，深知算法的重要性，最近正在刷题中，努力提高中

这个最优解的算法并不算我想到的，是我在请教一个算法很厉害的人给我提示的，才想到的这种算法，下面我讲一下这种算法的思想和具体的解法，后面我会贴上算法代码，供大家学习参考，如有不足，希望大家提出。谢谢！

在做这道题目之前我们需要知道一点就是，每组数据里面只可以有一个这样的数字

我们在遍历数组的时候可以用两个变量，一个cand用来保存遍历到当前数组的数字；另外一个变量times是用来记录当前数字出现的次数；在遍历第一个数的时候将times初始化为1，cand初始赋值为第一个数；接下来遍历数组

1、如果下一个数字与cand当前保存的数相同则times+1

2、如果下一个数字与cand当前保存的数字不同则times-1

3、当times为0的时候，cand需要重新被赋值为下一个数，times被重新赋值为1，一直到遍历结束；

下面举个例子，比如有一个数组{0,1,2,1,1}，按照上面的算法思想，步骤如下

1、开始的时候cand先被赋值为0，times为1

2、遍历到下一个数，1与cand不同，则times-1为0,；又times为0，则cand又被重新赋值为0，times又被重新赋值为0

3、同样的道理，遍历下一个数字，2与cand不同，则times-1为0；又times为0，则cand又被重新赋值为2，times又被重新赋值为1

4、继续遍历下一个数字，1与cand不同，则times-1为0；又times为0，则cand被赋值为1，times为1

5、继续遍历，1与cand相同，times+1，times为2；最后我们返回的就是将times设为2的cand

完整的算法代码如下

//a代表数组，length代表数组长度
int FindOneNumber(int* a, int length)
{
    int candidate = a[0];
    int nTimes = 1;
    for (int i = 1; i < length; i++)
    {
        if (nTimes == 0)
        {
            candidate = a[i];
            nTimes = 1;
        }
        else
        {
            if (candidate == a[i])
                nTimes++;
            else
                nTimes--;
        }
    }
    return candidate;
}