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; }新聞熱點
疑難解答
