LeetCode 169. Majority Element

用户头像
liu_liu
关注
发布于: 2020 年 09 月 13 日
LeetCode 169. Majority Element

问题描述



给定一个数组,长度为 n,找到众数。众数是指出现次数大于「n/2」的元素。



假定数组非空,且众数一定存在。



栗 1:

输入:[3, 2, 3]
输出:3



栗 2:

输入:[2,2,1,1,1,2,2]
输出:2



解题思路



题目其实并不难,可以有很多种解法,比如:



  • 使用 map 记录元素出现的次数

  • 先排序,然后取中间位的元素

  • ...



那为什么还要记录这道题目的解法呢?因为我在解法中看到了一个比较独特的思路,即摩尔投票算法。下面来介绍一下它的原理。



原理与实现



它的主要原理是将不同的数进行抵消,最终剩下的不能抵消的数则为所求结果。



具体实现如下:



  • 用 array 记录不能被抵消的数,用 result 记录删除抵消数据对之后的结果。

  • 遍历原数组,将元素与 array 中的数据进行比较。

- 如果不相同,则可以抵消。更新 array 和 result,即在 array 和 result 中删除抵消的数据;

- 如果相同,则不能抵消,元素加入到 array。

  • 最后,array 和 result 中就是所求得的结果。



举例说明



举个栗子,比如数组 list = [1, 3, 1, 2, 1, 1]。下面来逐个遍历数组元素。



  • 取出 1。由于初始 array = [],没有可以抵消的数。将 1 添加到 array,此时 array = [1], result = [1, 3, 1, 2, 1, 1]

  • 取出 3。由于 array = [1], 1 与 3 不相等,可以抵消。此时 array = [], 在 result 中删除 1 和 3,result = [1, 2, 1, 1]

  • 取出 1。由于 array = [],将 1 添加到 array。此时 array =[1], result = [1, 2, 1, 1]

  • 取出 2。由于 array = [1],2 与 1 不相等,可以抵消。此时 array = [], 在 result 中删除 1 和 2,result = [1, 1]

  • 取出 1。由于 array = [],将 1 直接添加到 array。此时 array = [1],result = [1, 1]

  • 取出 1。由于 array = [1],它们相同不能抵消,将 1 添加到 array。此时 array = [1, 1],result = [1, 1]



在这过程中,抵消掉了 (1,3)、(1,2) 两个数据对,所以还剩下 [1,1]。因此 1 为所求得的结果。



算法简化



在上述实现中,array 和 result 是我们为了方便理解算法假想出来的,其实并不需要。只需使用两个变量 majority 和 count 进行记录,来简化算法。



其中 majority 记录不能被抵消的元素,count 记录不能被抵消元素的个数。算法调整如下:



  • count == 0,说明没有可以被抵消的元素,那么 majority 更新为当前元素count += 1

  • count > 0,说明有可以被抵消的元素。如果当前元素与 majority 不等,则可以抵消,count -= 1;反之 count += 1



最后的 majority 即为所求值。



代码实现



js 版代码实现如下:

var majorityElement = function(nums) {
if (nums && nums.length > 0) {
// 不能被抵消的数
let majority = nums[0]
// 记录不能抵消的数量
let count = 1
let i = 1
while (i < nums.length) {
const num = nums[i]
// 没有可以抵消的,直接更新
if (count === 0) {
// 更新 majority
majority = num
count = 1
} else {
if (majority !== num) {
// 可以抵消
count -= 1
} else {
count += 1
}
}
i += 1
}
return majority
}
}

栗子重演

对应上面的栗子,我们再来走一遍流程:



  • 取出 1。由于是数组第一个元素,此时设置 majority = 1,count= 1

  • 取出 3。由于它与 majority 不等,可抵消。此时,更新 count = 0,majority 更不更新无所谓,因为它有自己的更新时机。

  • 取出 1。由于 count = 0,没有可以被抵消的元素。此时更新 majority = 1,count = 1

  • 取出 2。由于它与 majority 不等,可抵消。此时,更新 count = 0,同样,majority 保持不变。

  • 取出 1。由于 count = 0,没有可以被抵消的元素。此时,更新 majority = 1,count = 1

  • 取出 1。它与 majority 相等,不可抵消。此时,更新 count = 2



最后,majority = 1 即为结果。



参考资料:





发布于: 2020 年 09 月 13 日 阅读数: 18
用户头像

liu_liu

关注

不要相信自己的记忆力 2017.11.13 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode 169. Majority Element