本文共 1574 字，大约阅读时间需要 5 分钟。

链接：

大意：

给定一个整数数组nums，要求找出数组中出现次数超过nums.length / 3次的所有数字。规定：使用时间复杂度为O(n)，空间复杂度为O(1)的方法解决。例子：

思路：

全军覆没。思路参考链接：

代码：

class Solution{    public List
   
     majorityElement(int[] nums) {        List
    
      resultList=new ArrayList<>();        if (nums == null || nums.length == 0){            return resultList;        }        //初始化，定义两个候选人以及对应的票数        int candidateA=nums[0];        int candidateB=nums[0];        int countA=0;        int countB=0;        // 遍历数组        for (int num:nums){            if (num==candidateA){ //投A                countA++;                continue;            }            if (num==candidateB){// 投B                countB++;                continue;            }            //此时A,B都不投,检查是否有票数为0情况，如果为0，则更新候选人            if (countA==0){                candidateA=num;                countA++;                continue;            }            if (countB==0){                candidateB=num;                countB++;                continue;            }            //此时两个候选人的票数都大于1，且当前选名不投AB，那么A,B对应的票数都要--;            countA--;            countB--;        }        // 上一轮遍历找出了两个候选人，但是这两个候选人是否均满足票数大于N/3仍然没法确定，需要重新遍历，确定票数        countA=0;        countB=0;        for (int num:nums){            if (num==candidateA){                countA++;            }else if (num==candidateB){                countB++;            }        }        if (countA > nums.length/3){            resultList.add(candidateA);        }        if (countB > nums.length/3){            resultList.add(candidateB);        }        return resultList;    }}
    
   

结果：

结论：

好菜啊 

转载地址：http://oaesi.baihongyu.com/