169. Majority Element

题目：

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

链接： http://leetcode.com/problems/majority-element/

2/20/2017, Java

performance不好，为什么？

 1 public class Solution {
 2     public int majorityElement(int[] nums) {
 3         HashMap<Integer, Integer> dict = new HashMap<Integer, Integer>();
 4         int count = 0;
 5         if (nums.length == 1) return nums[0];
 6 
 7         for(int i = 0; i < nums.length; i++) {
 8             if (dict.containsKey(nums[i])) {
 9                 count = dict.get(nums[i]);
10                 if (count + 1 > nums.length / 2) return nums[i];
11                 dict.put(nums[i], count + 1);
12             } else {
13                 dict.put(nums[i], 1);
14             }
15         }
16         return 0;
17     }
18 }

因为有Boyer-Moore Majority vote algorithm!

留给二刷，并且要学会多于特定比例的情况。