算法记录

LeetCode 题目：

 &emsp;&emsp;给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 <hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">

说明

一、题目

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

二、分析

题目很简单，我们可以直接使用 hash 来进行计数，最后遍历输出即可，但是这样需要存储的数据太多，不够简洁。

我们这里使用摩尔投票来进行计算，对于 [摩尔投票]() 不懂的可以看一下我的这篇文章。

class Solution {    public List<Integer> majorityElement(int[] nums) {        int[][] count = new int[2][2];        for(int num : nums) {            if(count[0][0] > 0 && num == count[0][1]) count[0][0]++;            else if(count[1][0] > 0 && num == count[1][1]) count[1][0]++;            else if(count[0][0] == 0) {                count[0][0]++;                count[0][1] = num;            } else if(count[1][0] == 0) {                count[1][0]++;                count[1][1] = num;            } else {                count[0][0]--;                count[1][0]--;            }        }        count[0][0] = 0;        count[1][0] = 0;        for(int num : nums) {            if(count[0][1] == num) count[0][0]++;            else if(count[1][1] == num) count[1][0]++;        }        List<Integer> ret = new ArrayList();        for(int i = 0; i < 2; i++) {            if(count[i][0] > nums.length / 3) ret.add(count[i][1]);        }        return ret;    }}

<hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">

总结

摩尔投票的应用。

原文：https://juejin.cn/post/7100527398856163359