2015年6月29日星期一

[LeetCode] Majority Element II

Problem:

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.

Thinking:

这道题和LintCode的Majority Number II很像,但是稍有不同,需要考虑一个特殊情况:

Input:
[1,2]
Expected:
[1,2]

When there are two different elements in the array, both of the two elements appear more than n/3 times.

Java Code (写得这么长T_T):

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        int candidate1 = 0;
        int candidate2 = 0;
        int count1 = 0;
        int count2 = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (count1 == 0) {
                candidate1 = nums[i];
            } else if (count2 == 0) {
                candidate2 = nums[i];
            }
            
            if (nums[i] == candidate1) {
                count1++;
            }
            else if (nums[i] == candidate2) {
                count2++;
            } else {
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == candidate1) {
                count1++;
            }else if (nums[i] == candidate2) {
                count2++;
            }
        }
        
        if (count1 > nums.length / 3) {
            result.add(candidate1);
        }
        if (count2 > nums.length / 3) {
            result.add(candidate2);
        }
        
        return result;
    }
}



2 条评论:

  1. 这道题是怎么想到这个思路的?我拿到这个问题,我会首先想是否可以将原来的数组拆成两部分,但是没有找到方法。
    虽然代码可以AC,但是我不明白为什么能够AC

    回复删除
    回复
    1. 思路大概是,要找的是出现次数大于 n/3 的数,所以这份代码里面维护四个变量,分别是 candidate1 和它对应的次数 count1,candidate2 和它对应的次数 count2,一遍遍历,最后剩下的两个 candidate 一定是出现次数超过 n/3 的。然后用第二遍遍历做验证(如果不做的话,在 Input:[1] 这类 test case 就会出错)

      删除