大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个数组，返回其中的多数元素。”
2、题目描述
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1： 输入： nums = [3,2,3] 输出： 3
示例 2： 输入： nums = [2,2,1,1,1,2,2] 输出： 2
二、解题
1、思路分析
这道题要求出出现次数大于n/2的元素，暴力方法可以使用遍历美剧数组中的每个元素，再遍历一遍数组统计其出现次数。
但是这个方法的时间复杂度为O(n2)，与题意不符。需要将时间复杂度降到O(n2)以下。
容易想到的可以使用哈希表，去掉一层遍历，将时间复杂度降到O(n)。
2、代码实现
代码参考：
class Solution { private Map<Integer, Integer> countNums(int[] nums) { Map<Integer, Integer> counts = new HashMap<Integer, Integer>(); for (int num : nums) { if (!counts.containsKey(num)) { counts.put(num, 1); } else { counts.put(num, counts.get(num) + 1); } } return counts; } public int majorityElement(int[] nums) { Map<Integer, Integer> counts = countNums(nums); Map.Entry<Integer, Integer> majorityEntry = null; for (Map.Entry<Integer, Integer> entry : counts.entrySet()) { if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) { majorityEntry = entry; } } return majorityEntry.getKey(); } }
3、时间复杂度
时间复杂度：O(n)
其中n是数组nums的长度，遍历一遍数组，在遍历结束对哈希表进行遍历，因为哈希表占用的空间为O(n)，因此总时间复杂度为O(n)。
空间复杂度：O(n)
其中n是数组nums的长度。
三、总结
使用哈希表来存储每个元素以及出现的次数。
对于哈希表中每个键值对，键表示元素，值表示次数。
用循环遍历数组，并将数组中的每个元素加入哈希表中。
遍历哈希表中所有键值对，返回值最大的键。
