Majority Element

Majority Element
给定一个长度为n的数组，从中找出出现次数最多的元素，这个元素出现的次数多余[n/2]次。假设数组不为空并且始终存在一个majority元素。

解决这道题有很多种方法，但是时间复杂度和空间复杂度各不相同，在这里我们用三种不同的方法解这道题。

1，最简单的方法就是先将数组排好序，根据题意我们知道，出现最多的元素肯定是中间的元素。
我们直接调用Arrays的sort方法，这样时间复杂度是O(nlogn)，空间复杂度为O(1)。代码如下：

public class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        if(nums.length==1) {
            return nums[0];
        } else {
            return nums[nums.length / 2];
        }
    }
}

2，第二种方法我们可以用哈希表来记录元素出现的次数，直到找到一个元素出现次数多于数组长度的一半就返回。这样空间复杂度为O(n)，时间复杂度为O(n)。相当于用空间换时间，实现代码如下：

public class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        int result = 0;
        for(int i = 0; i < nums.length; i++) {
            if(hm.containsKey(nums[i])) {
                hm.put(nums[i], hm.get(nums[i])+1);
            } else {
                hm.put(nums[i], 1);
            }
            if(hm.get(nums[i]) > nums.length/2) {
                    result = nums[i];
                    break;
            }   
        }
        return result;
    }
}

3，这是一个很巧妙的算法，叫做Moore Voting Algorithm。它专门用来处理出现次数最多元素的，它的时间复杂度为O(n)，空间复杂度为O(1)。它的思想是在数组中找成对的元素，如果它们的值不相等，就忽略它们，相当于把它们删除；如果它们的值相等，那么就用一个变量来记录重复的次数。通过代码来理解更直观，代码如下：

public class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int result = 0;
        for(int num : nums) {
            if(count == 0) result = num;
            if(result != num) {
                count --;
            } else {
                count ++;
            }
        }
        return result;
    }
}