[数据结构与算法]Leetcode-169 多数元素 229 求众数

题目描述：

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

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

示例?1：

输入：[3,2,3]
输出：3
示例?2：

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

进阶：

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

摩尔投票算法：抵消阶段+计数阶段? ??时间复杂度为 O(n)、空间复杂度为 O(1)

假设正确答案为maj

1. 如果候选人不为maj 则 maj会和其他非候选人一起反对候选人,因为maj数量多，所以候选人一定会下台(maj==0时发生换届选举)
2. 如果候选人是maj , 则maj会支持自己，其他候选人会反对，同样因为maj数量多，所以maj 一定会成功当选

?适用于求得给定序列中数量超过1/2的元素值

class Solution {
    public int majorityElement(int[] nums) {
        if(nums==null||nums.length==0)
            return -1;
        int temp=nums[0];
        int count=1;
        for(int i=1;i<nums.length;i++)
        {
            if(count==0)
                temp=nums[i];
            if(nums[i]==temp)
                count++;
            else
                count--;
        }
        //由于题目中给定 总是存在多数元素 的条件，所以将计数阶段省略
        return temp;
    }
}

题目描述：

给定一个大小为?n?的整数数组，找出其中所有出现超过?? n/3 ??次的元素。

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

示例?1：

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

输入：nums = [1]
输出：[1]
示例 3：

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

提示：

1 <= nums.length <= 5 * 10^4
-10^9 <= nums[i] <= 10^9

摩尔投票算法升级

要找到出现次数超过?? n/k ?的元素，就要设置k-1个候选人

//先将当前值与候选人1比较，若相等则投票加1，更换当前值
//                       若不相等则与候选人2比较，若相等则投票加1，更换当前值
//                                              若不相等，查看投票数1，若为0则更换候选人，投票数记为1，更换当前值
//                                                                   若不为0则查看投票数2，若为0则更换候选人，投票数记为1，更换当前值
若不为0则投票数1、投票数2同时减1，更换当前值
class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result=new ArrayList<Integer>();
        if(nums==null||nums.length==0)
            return result;
        int temp1=nums[0];
        int temp2=nums[0];
        int count1=0;
        int count2=0;
        for(int i=0;i<nums.length;i++)
        {
            if(nums[i]==temp1)
            {
                count1++;
                continue;
            }
            if(nums[i]==temp2)
            {
                count2++;
                continue;
            }
            if(count1==0)
            {
                temp1=nums[i];
                count1++;
                continue;
            }     
            if(count2==0)
            {
                temp2=nums[i];
                count2++;
                continue;
            }  
            count1--;
            count2--;
        }
        //计数阶段，验证是否真的超过n/3
        count1=0;
        count2=0;
        for(int i=0;i<nums.length;i++)
        {
            if(nums[i]==temp1)
                count1++;
            if(nums[i]==temp2)
                count2++;
        }
        if(count1<=nums.length/3&&count2<=nums.length/3)
            return result;
        else if(count1<=nums.length/3)
        {
            result.add(temp2);
            return result;
        }
        else if(count2<=nums.length/3)
        {
            result.add(temp1);
            return result;
        }
        if(temp1!=temp2)
        {
            result.add(temp1);
            result.add(temp2);
            return result;
        }
        else
        {
            result.add(temp1);
            return result;
        }
    }
}