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

柔光的暖阳◎ 2022-05-24 11:16 156阅读 0赞

##### 题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字，否则返回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;
    }