169. Majority Element

Description

1. Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
   You may assume that the array is non-empty and the majority element always exist in the array.
2. Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Solution

[leetcode 169] Majority Element

这道题比较简单，如果有一个数字在数组中出现的次数超过了数组长度的一半，那么我们拿这个数字和其它的数字进行抵消，剩下的肯定是这个数字，那么顺着这个思路写出如下代码：

public int majorityElement(int[] nums) {
    if(nums==null||nums.length==0)return -1;
    int res,num;
    res=nums[0];
    num=1;
    for(int i=1;i<nums.length;i++){
        if(nums[i]!=res){
            num--;
            if(num<=0){
                res=nums[i];
                num=1;
            }
        }else num++;
    }
    return res;
}

[leetcode 229] Majority Element II

这道题倒是难了起来，但是如果用前面的思路进行扩展的话，也是很easy的。我们用两个数来分别代表数组中不同的数字，记录这两个数字出现的个数，遍历其它元素，如果和这两个数字中一个相等，就将对应个数加1；如果个数为0，就用当前元素替换；如果都不相等，个数也不为0，那么相对的两个元素的个数都需要-1。注意为什么用两个元素，因为一个数组中出现次数超过n/3的元素最多只能有2个，我们用两个变量记录该数组中出现次数最多的两个元素，然后再判断这两个元素是否都超过了n/3，代码如下：

public List<Integer> majorityElement(int[] nums) {
    List<Integer> list=new ArrayList<>();
    if(nums==null||nums.length==0)return list;
    int temp1,temp2,num1,num2;
    temp1=temp2=nums[0];
    num1=num2=0;
    for(int i=0;i<nums.length;i++){
        if(nums[i]==temp1)num1++;
        else if(nums[i]==temp2)num2++;
        else if(num1==0){
            temp1=nums[i];
            num1=1;
        }else if(num2==0){
            temp2=nums[i];
            num2=1;
        }else {
            num1--;
            num2--;
        }
    }
    num1=num2=0;
    for (int i=0;i<nums.length;i++){
        if(nums[i]==temp1)num1++;
        else if(nums[i]==temp2)num2++;
    }
    if(num1>nums.length/3)list.add(temp1);
    if(num2>nums.length/3)list.add(temp2);
    return list;
}