LeetCode Majority Element【Easy】

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

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

解決

題目的意思是給定一個給定的數(shù)組中，找出多數(shù)的元素，假定數(shù)組長度為n，則這個多數(shù)元素定義為該元素在數(shù)組中出現(xiàn)的次數(shù)大于[n/2]次。
這里給出兩種解決辦法，代碼和部分的注釋如下。

hash法

 /**
   * 使用map key 存儲數(shù)組，value 統(tǒng)計出現(xiàn)的次數(shù)
   * @param nums
   * @return
   */
  public int majorityElement(int[] nums) {
      Map<Integer,Integer> map = new HashMap<>();
      int res =0;
      for(int i:nums){
          map.put(i,map.get(i)==null?1:map.get(i).intValue()+1);
          if(map.get(i).intValue()>(nums.length/2)){
              res=i;
          }

      }
      return res;
  }

數(shù)組方法

 /**
     * 排序，取數(shù)組mid，最后返回num[mid]值即為結(jié)果
     * @param nums
     * @return
     */
    public int majorityElement2(int[] nums) {
        Arrays.sort(nums);
        int t = nums.length/2;
        return nums[t];
    }