Majority Element

package cn.edu.xidian.sselab.array;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
*
* @author zhiyong wang
* title: Majority Element
* content:
*        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.
*
*/
public class MajorityElement {

   //从头开始遍历数组中所有的数，用一个HashMap记录每个数字及数字出现的次数，选出次数大于数组个数一半的数值
   public int majorityElement(int[] nums){
       int length = nums.length;
       int result = nums[0];
       Map<Integer,Integer> times = new HashMap<Integer,Integer>();
       for(int i=0;i<length;i++){
           if(times.containsKey(nums[i])){
               int time = times.get(nums[i]) + 1;
               if(time >= length / 2){
                   result = nums[i];
                   break;
               }
               times.put(nums[i], time);
           }else{
               times.put(nums[i], 0);
           }
       }
       return result;
   }

   //从leetcode学习的方法，非常巧妙，调用Arrays自动排序接口，因为搜求结果一定会大于一半，所以中间的数值一定就是所求的值
   public int majorityElement1(int[] nums){
       Arrays.sort(nums);
       return nums[nums.length / 2];
   }

}