找出数组中出现次数超过一半的数+ 寻找众数 + 摩尔投票法

r囧r小猫 2022-05-30 02:39 220阅读 0赞

# 排序 #

就是先做排序，然后找中位数

# map统计 #

直接使用map统计出现次数，然后遍历map即可

# 缩小范围 #

每次取出两个不同的数，剩下的数字中重复出现的数字肯定比其他数字多，将规模缩小化。如果每次删除两个不同的数（不管包括不包括最高频数），那么在剩余的数字里，原最高频数出现的频率一样超过了50%，不断重复这个过程，最后剩下的将全是同样的数字，即最高频数。此算法避免了排序，时间复杂度只有O(n)，空间复杂度为O(1)。

这个就是典型的摩尔投票法，可以和这个链接[leetcode 229. Majority Element II 摩尔投票法 Moore Voting + 要记住验证投票结果哦][leetcode 229. Majority Element II _ Moore Voting _] 一起学习

#include <iostream>
    
    int FindMostData(int arr[], int len)
    {
        int findNum = 0; // 出现次数超过一半的数；
        int count = 0; // 只要最终count > 0，那么对应的findNum就是出现次数超过一半的数；
    
        // 循环过程中，i每增加一次，就相当于把i之前的所有元素（除了满足“findNum == arr[i]”条件的arr[i]，这些对应元素用“count++”来标记）都抛弃了，但是之后每当执行一次“ count-- ”时，又会从前面这些已保留的且等于findNum的元素中删除一项，直到count == 0，再重选findNum；
        for (int i = 0; i < len; i++)
        {
            if (count == 0) // count为0时，表示当前的findNum需要重选；
            {
                findNum = arr[i];
                count = 1;
            }
            else
            {
                if (findNum == arr[i])
                    count++;
                else
                    count--;
            }
        }
    
        return findNum;
    }
    
    int main(int argc, const char * argv[]) {
    
        int arr[] = {
       1,2,3,2,5,2,2,6,2,2,2};
        int len = sizeof(arr)/sizeof(int);
    
        printf("出现次数超过一半的数是 %d\n", FindMostData(arr, len));
    
        return 0;
    }

[leetcode 229. Majority Element II _ Moore Voting _]: http://blog.csdn.net/JackZhang_123/article/details/78083283