Leetcode - Majority Element

My code:

import java.util.HashMap;

public class Solution {
    public int majorityElement(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        if (nums.length == 1)
            return nums[0];
        HashMap<Integer, Integer> h = new HashMap<Integer, Integer>();
        int upLimit = nums.length / 2;
        for (int i = 0; i < nums.length; i++) {
            if (!h.containsKey(nums[i]))
                h.put(nums[i], 1);
            else {
                int temp = h.get(nums[i]);
                temp++;
                if (temp > upLimit)
                    return nums[i];
                else
                    h.put(nums[i], temp);
            }   
        }
        return 0;
    }
}

My test result:

这次作业感觉还是比较简单吧。我用了一个hash map。
key -> nums[i] value-> nums[i] 出现的次数。
如果 > n /2; 就直接返回吧。

但是还有许多做法，此题。比如，排序，然后直接去数组中间值。
因为，出现次数 > n /2， 所以这个数一定会包括最中间的那个值。链接如下：
http://www.programcreek.com/2014/02/leetcode-majority-element-java/

public int majorityElement(int[] nums) {
    Integer n = null;
    int c = 0;
    for (int i = 0; i < nums.length; i++) {
        if (n != null && n.compareTo(nums[i]))
            c++;
        else if (c == 0)
            n = new Integer(nums[i]);
        else if (n == null) {
            c = 1;
            n = new Integer(nums[i]);
        }
        else if (!n.compareTo(nums[i])) {
            c--;
        }
    }
    c = 0;
    for (int i = 0; i < nums.length; i++) {
        if (n.compareTo(nums[i]))
            c++;
    }
    
    if (c >= (nums.length / 3))
        return n;
    else
        return null;
}

http://www.programcreek.com/2014/07/leetcode-majority-element-ii-java/
**
总结：Array。简单
**

Anyway, Good luck, Richardo!

My code:

public class Solution {
    public int majorityElement(int[] nums) {
        if (nums == null || nums.length == 0)
            return -1;
        int major = nums[0];
        int counter = 1;
        for (int i = 1; i < nums.length; i++) {
            if (major != nums[i]) {
                counter--;
                if (counter == 0) {
                    major = nums[i];
                    counter = 1;
                }
            }
            else
                counter++;
        }
        return major;
    }
}

直接用投票算法做的，比较简单。

然后我改写了下形式，使得更加直接明了，并且可以应对数组中不存在majority的情况。代码如下：

public class Solution {
    public int majorityElement(int[] nums) {
        if (nums == null || nums.length == 0)
            return -1;
        Integer c1 = null;
        int counter1 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (c1 != null && c1.intValue() == nums[i])
                counter1++;
            else if (counter1 == 0)
                c1 = new Integer(nums[i]);
            else
                counter1--;
        }
        
        /** make sure whether this element is majority */
        if (c1 == null)
            return -1; // means has no majority
        counter1 = 0;
        for (int i = 0; i < nums.length; i++)
            if (nums[i] == c1.intValue())
                counter1++;
        if (counter1 > nums.length / 2)
            return c1.intValue();
        else
            return -1;
    }
}

具体总结见 Majority 2
http://www.jianshu.com/p/3ccbc915f3a1

Anyway, Good luck, Richardo!