169. Majority Element

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

解决

题目的意思是给定一个给定的数组中，找出多数的元素，假定数组长度为n，则这个多数元素定义为该元素在数组中出现的次数大于[n/2]次。
这里给出两种解决办法，代码和部分的注释如下。

hash法

 /**
   * 使用map key 存储数组，value 统计出现的次数
   * @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;
  }

数组方法

 /**
     * 排序，取数组mid，最后返回num[mid]值即为结果
     * @param nums
     * @return
     */
    public int majorityElement2(int[] nums) {
        Arrays.sort(nums);
        int t = nums.length/2;
        return nums[t];
    }