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

65 阅读 0 评论 43 点赞

我是靠谱客的博主冷静奇迹，最近开发中收集的这篇文章主要介绍数组中出现次数超过一半的数字，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：数组中一个数字出现的次数超过数组长度的一半，请找出这个数字。如：输入[2,7,7,3,,7]，输出结果为7，如果不存在该数字，则输出结果为-1。

解法一、

如果存在这个数字，那么排序之后位于数组中间的数字就一定是该数字。找到这个数字之后，再判断这个数字出现的次数是否大于数组长度的一半即可。

代码省略。

解法二、

数字出现的次数超过数组长度的一半，意味着该数字出现的次数比其它所有数字出现的次数还多。可以通过记录数组中的数字以及次数来解决这个问题：遍历数组，如果下一个数字与上一个数字相同，则次数+1，否则次数-1，当次数为0的时候，则置为1，并重新记录该数字。最后的次数如果大于0，则表示数组中可能存在一个数字出现的次数超过数组长度的一半,再判断这个数字出现的次数是否大于数组长度的一半即可。代码如下：

int moreThanHalfNum(const vector<int>& array)
{
    int ret = array[0];
    int times = 1;
    for (int i = 1; i < array.size(); ++i) {
        if (times == 0) {
            ret = array[i];
            times = 1;
        } else if (array[i] == ret) {
            times++;
        } else {
            times--;
        }
    }

    if (times > 0) {
        times = 0;
        for (int i = 0; i < array.size(); ++i) {
            if (array[i] == ret) {
                times++;
            }
        }
        if (times > array.size()/2) {
            return ret;
        }
    }
    return -1;
}


int main()
{
    vector<int>a = {0, 1, 1};
    vector<int>b = {0, 1, 1, 2};
    vector<int>c = {0, 3, 3, 2, 3};
    vector<int>d = {0, 5, 5, 2, 5, 3, 4, 4, 4, 5, 5, 5, 5};
    cout << "a = " << moreThanHalfNum(a) << endl;
    cout << "b = " << moreThanHalfNum(b) << endl;
    cout << "c = " << moreThanHalfNum(c) << endl;
    cout << "d = " << moreThanHalfNum(d) << endl;
    return 0;
}

结果：