找到数组中出现次数超过数组长度一半的元素

51 阅读 0 评论 34 点赞

我是靠谱客的博主缥缈鲜花，最近开发中收集的这篇文章主要介绍找到数组中出现次数超过数组长度一半的元素，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字，否则返回0。比如长度为9的数组`{1，2，3，2，2，2，5，4，2}`，数组中2出现了5次，超过数组长度的一半，因此输出2。

方法1：因为这个数字超过了数组长度的一半，所以，我首先想到的是将数组排序，排序后中间的元素就是我们要找的数据，然后再判断它出现的次数是不是超过了数组长度的一半。

#include <algorithm>
#include <vector>
using namespace std;
int MoreThanHalfNum_Solution(vector<int> numbers)
{
    vector<int>::iterator it = numbers.begin(); //先排序，该数字一定是中位数，
    sort(it, numbers.end());        // 再统计该数字出现的次数，判断是否满足超过数组长度的一半
    int mid = numbers.size() / 2;
    int count = 0;
    int size = numbers.size();
    for (int i = 0; i < size; i++)
    {
        if (numbers[mid] == numbers[i])
            count++;
        if (count > size/2)
            return numbers[mid];
    }
    return 0;
}

方法2：首先，找到原数组的一个范围，然后借助另一个数组，以原数组中的数据为新数组的下标，统计原先数组每一个元素出现的次数，然后再新数组中找出现次数超过数组长度一半的元素。

int MoreThanHalfNum_Solution(vector<int> numbers)
{
    int size = numbers.size();
    int max = numbers[0];
    int min = numbers[0];
    for (int i = 0; i < size; i++)
    {
        if (numbers[i] < min)
            min = numbers[i];
        if (numbers[i] > max)
            max = numbers[i];
    }
    vector<int> v(max - min + 2);
    for (int i = 0; i < size; i++)
        v[numbers[i]]++;
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i] > size / 2)
            return i;
    }
    return 0;
}

但是这样做，首先要知道原数组中元素的范围，需要遍历一遍，找到最大值和最小值，然后才能开辟新空间；另外，如果原数组中的数据范围很大，那么这个新数组会占用很大的空间。
既然如此，又想到了用unordered_map来记录数组中数字出现的次数。

#include <unordered_map>
int MoreThanHalfNum_Solution(vector<int> numbers)
{
    unordered_map<int, int> hp;
    int size = numbers.size();
    for (int i = 0; i < size; i++)
    {
        if (hp.find(numbers[i]) != hp.end())//找到了，出现次数+1
            hp.insert(make_pair(numbers[i], hp[numbers[i]]+=1));
        else//没找到，出现次数为1
            hp.insert(make_pair(numbers[i], 1));
        if (hp[numbers[i]] > size / 2)
            return numbers[i];
    }
    return 0;
}

方法3：我们要找的数字超过了数组长度的一半，那么我们可以这样做：利用两个辅助变量，一个记录数字出现的次数，一个记录数字；当后面的数字与其相等次数加1，不同减1，当次数为0时，记录数字就换成此时的数字。最终得到的数字有可能是所求，但是还不一定（例如1,2,3,4,5,6,1,1），还需要重新遍历一次数组，查看此值出现是否超过数组长度一半。

以{1，2，3，2，2，2，5，4，2}为例：

先定义两个变量num=1，count=1;
然后从第二个元素开始遍历，2不等于num，count--变为0，即：2与1抵消了；此时让num=2，count置回1；
第三个元素3不等于num，count--变为0，此时让num=3，count置回1；
第四个元素2不等于num，count--变为0，此时让num=2，count置回1；
第五个元素2等于num，count++变为2，此时直接遍历下一个元素；
第六个元素2等于num，count++变为3，此时num仍为2；
第七个元素5不等于num，count--变为2，此时num仍为2；
第八个元素4不等num，count--变为1，此时num仍为2；
第九个元素2等于num，count++变为2，此时num仍为2；
最后再遍历一遍数组，看num出现次数是否超过数组长度一半。

int MoreThanHalfNum_Solution(vector<int> numbers)
{
    int size = numbers.size();
    int num = numbers[0];
    int count = 1;
    for (int i = 1; i < size; i++)
    {
        if (numbers[i] == num)
            count++;
        else
            count--;
        if (count == 0)
        {
            num = numbers[i];
            count = 1;
        }
    }
    count = 0; // 统计一下这个数字出现的次数，判断是不是超过数组长度的一半
    for (int i = 0; i < size; i++)
    {
        if (numbers[i] == num)
            count++;
    }
    if (count * 2 > size)
        return num;
    return 0;
}

方法四：这个数字出现的次数超过数组长度的一半，那么这个数字一定是中位数。利用快速排序的思想，找一个数字，经过一次Partion之后，小于该数字的元素位于其左边，大于它的在它的右边，此时判断该数字的位置是不是数组的中间位置，如果是，则返回；如果该数字的位置大于数组中间位置，则说明中位数在它的左边；否则，在它的右边找。递归下去，就可以找到了。

int Partion(vector<int>& v, int left, int right)
{
    int key = v[right-1];
    int index = left;
    int small = index - 1;
    for (index = left; index < right; index++)
    {
        if (v[index] < key)
        {
            ++small;
            if (small != index)
                swap(v[small], v[index]);
        }
    }
    ++small;
    swap(v[small], v[right - 1]);
    return small;
}
int MoreThanHalfNum_Solution(vector<int> numbers)
{
    int left = 0;
    int right = numbers.size();
    int div = Partion(numbers, left, right);
    int mid = right >> 1;
    while (div != mid)//选中的数字经过处理，左边的都比他小，右边都比他大，如果他的位置是n/2，就是中位数
    {
        if (div > mid)
        {
            right = div;
            div = Partion(numbers, left, right);
        }
        else
        {
            left = div + 1;
            div = Partion(numbers, left, right);
        }
    }
    int num = numbers[mid];
    int count = 0;
    for (int i = 0; i < numbers.size(); i++)
    {
        if (num == numbers[i])
            count++;
        if (count > numbers.size() / 2)
            return num;
    }
    return 0;
}