问题描述

这是LeetCode上的一道算法题，博主整理了三种解题思路和方法，希望可以帮助大家提升算法的思维。

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：[3,2,3]
输出：3

示例 2：

输入：[2,2,1,1,1,2,2]
输出：2

进阶：

尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

来源：力扣（LeetCode）
链接：169.多数元素

一、解法1（双引用暴力求解）：

这是一个时间复杂度为O（n*n）的算法，也是大多数人能想出来的算法。
每次从数组中取出一个元素，扫描一遍数组，查看这个元素出现的次数，当前元素出现次数 >= n / 2,即为答案。
代码如下：

public static void main(String[] args) {
        int[] arr = new int[]{2,2,1,1,1,2,2};
        int sum = find(arr);
        System.out.println(sum);
    }

    private static int find(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            int count=0;//设置计数器来统计每个元素出现的次数
            for (int j = 0; j < arr.length; j++) {
                if (arr[i]==arr[j]){
                    count++;
                }
            }
            if (count>arr.length/2){
            //当前元素出现次数 >n / 2,即为答案
                return arr[i];
            }
        }
        return -1;
    }

二、解法2（排序后直接返回中间值）：

举个例子：

当把这些数字排好序后，出现次数 >n / 2的元素一定是数组中间的元素。
代码如下：

public static void main(String[] args) {
        int[] arr = new int[]{2,2,1,1,1,2,2};
        Arrays.sort(arr);
        System.out.println(arr[arr.length >> 1]);
    }

由于排序算法的时间复杂度最优最快也是O（nlogn），所以这个解法还不够完美。

三、解法3（摩尔投票法）

下面介绍一个巨牛的时间复杂度只有O（n）的算法。（这个算法适用于任何众数问题）。

这个问题的本质就是候选人正票数和负票数的抵消问题，由于多数元素的得票数一定是>n/2，抵消后，票数一定是一个正数，最终胜出。

	public static void main(String[] args) {
        int[] arr = new int[]{2,2,1,1,1,2,2};
        System.out.println(majorityElement(arr));
    }


    public static int majorityElement(int[] arr) {
        // 默认候选人就是第一个元素
        int candidate = arr[0];
        int count = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == candidate) {
                count++;
            } else {
                count--;
                if (count == 0) {
                    // 更换候选人
                    candidate = arr[i];
                    count = 1;
                }
            }
        }
        return candidate;
    }

默认候选人就是第一个元素，然后给自己投一票（count=1），如果遇到相同的票则+1，否则-1。当count为0的时候换下一个人，并且重置票数为1（count=1）。

四、总结（摩尔投票法的推广）

摩尔投票法的应用—-众数问题
1.在一堆元素中，如果至多选择一个最多的元素，则他的票数>n/2.
2.在一堆元素中，如果之多选择两个最多的元素，则他的票数>n/3.
3.在一堆元素中，如果之多选择m个最多的元素，则他的票数>n/(m+1).

1.因为出现次数大于n/3的元素最多只有两个，所以最开始可以维护两个数字(num1,num2)和两个计数器(counter1,counter2)；
2.遍历数组，当数组中元素和num1或者num2相同，对应的counter1或者counter2加1；
3.如果counter1或counter2为0，将遍历到的该元素赋给num1或者nums2；
4.否则counter1和counter2都减1。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/81799.html