2015年10月23日星期五

Majority Element II leetcode

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.
public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        int n1 = 0, n2 = 0;
        int count1 = 0, count2 = 0;
        for (int s : nums) {
            if (count1 == 0) {
                n1 = s;
                count1++;
            } else if (count2 == 0 && n1 != s) {
                n2 = s;
                count2++;
            } else if (s == n1) {
                count1++;
            } else if (s == n2) {
                count2++;
            } else {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for (int s  : nums) {
            if (s == n1) {
                count1++;
            } else if (s == n2) {
                count2++;
            }
        }
        if (count1 > nums.length / 3) {
            res.add(n1);
        }
        if (count2 > nums.length / 3) {
            res.add(n2);
        }
        return res;
    }
}

没有评论:

发表评论