leetcode_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.

法1：网友方法，O(n) time O(1) space fastest solution

public int majorityElement(int[] num) { int major=num[0], count = 1; for(int i=1; i<num.length;i++){ if(count==0){ count++; major=num[i]; }else if(major==num[i]){ count++; }else count--; } return major; }

法2：先排序

public int majorityElement(int[] nums) { int half = (int) Math.ceil(nums.length/2.0); Arrays.sort(nums); int num =0; // 存放临时的major值 int major =nums[nums.length-1]; for(int i=0;i<nums.length;i++) { if(major != nums[i]){ major= nums[i]; num=0; num++; } else num++; if(num>=half) return major; } return -2147483648; }

法3：借助 Map，用时最多

public int majorityElement(int[] nums) { int half = (int) Math.ceil(nums.length/2.0); // < 元素值,对应的次数> Map<Integer, Integer> map = new HashMap<>(); for(int i=0;i<nums.length;i++) { if(!map.containsKey(nums[i])) map.put(nums[i], 1); else map.replace(nums[i], map.get(nums[i]), map.get(nums[i])+1); } for(int t :map.keySet()) if(map.get(t)>=half) return t; return -2147483648; }