【力扣热题100】[Java版] 刷题笔记-169. 多数元素

题目：169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

解题思路

该题目的核心点是：元素出现的次数大于 n/2

第一种：利用哈希集合，存入元素并统计数量，数量 大于  n/2 并返回

第二种：排序，将数组排序，排序后，中间元素一定就是多数元素，这里排序可以用冒泡或者快排，也可以直接利用数组的排序方法。

解题过程

第一种：哈希集合

class Solution {public int majorityElement(int[] nums) {if (nums.length == 1) {return nums[0];}Map<Integer,Integer> counts = new HashMap<Integer,Integer>();for(int i=0 ; i< nums.length; i++) {if (!counts.containsKey(nums[i])) {counts.put(nums[i], 1);} else {counts.put(nums[i], counts.get(nums[i])+1);}}int num = 0;Set<Map.Entry<Integer, Integer>> entries = counts.entrySet();for (Map.Entry<Integer, Integer> entry : entries) {if( entry.getValue() > (nums.length/2) ) {return entry.getKey(); }}return num;        }
}

第二种： 排序

class Solution {public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length / 2];}    }