「这是我参与11月更文挑战的第1天,活动详情查看:2021最后一次更文挑战」。
题目描述:
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
复制代码
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
复制代码
进阶:
- 尝试设计时间复杂度为
、空间复杂度为 的算法解决此问题。
思路分析
暴力解法
最容易想到的就是暴力解法了,遍历数组中的每个元素,再遍历一遍其出现的次数,但是该方法的时间复杂度是
,超出了我们题目进阶要求的时间复杂度
,所以pass。
哈希表
其次最容易想到的就是哈希表了,依稀记得做第一题,两数之和的时候就是这个解法。
这里同理,我们依然可以用哈希表来记录每个元素出现的次数,遍历数组,存入哈希表,key为数组中的元素,value为该元素出现的次数。然后我们只需要再遍历一遍这个哈希表就能找到我们的答案。
AC代码
class Solution {
fun majorityElement(nums: IntArray): Int {
val map = mutableMapOf<Int,Int>()
val half = nums.size / 2
for(num in nums) {
var n = 0
if(map.containsKey(num)) {
n = map[num]!!
}
map[num] = n + 1
if(n + 1 > half) return num
}
return -1
}
}
复制代码
排序
如果我们有一个元素的个数超过了 n/2 ,那么当我们对数组排序之后,中间的那个数一定是答案。这个不难想象,可以拿笔在纸上比划一下就明白了。
AC代码
class Solution {
fun majorityElement(nums: IntArray): Int {
Arrays.sort(nums)
return nums[nums.size / 2]
}
}
复制代码
总结
这一题虽然是简单题,我给出的两种方法也是比较容易想到的,但是看了题解才发现还有N种解法,包括 随机化, 分治, Boyer-Moore 投票算法。
尴尬,一个都没有听过,好好学习吧。
近期评论