leetcode讲解--169. Majority Element

LiuRhoRamen 发布于2019-07-25 11:21 / 2096人阅读

摘要：当时题目改成了小明收红包，找出现次数超过一般的那个红包，要求线性时间复杂度，也就是说不能用排序排序算法最优情况是。另外这个题在上的难度是哦，好伤心啊，当初的我连这题都没想出解法，真是够年轻啊。

169. Majority Element

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.

题目地址

唉，看到这题就想起了，当年，青葱岁月，菜鸡的我做阿里的笔试题，对的，就是这题。当时题目改成了小明收红包，找出现次数超过一般的那个红包，要求线性时间复杂度，也就是说不能用排序（排序算法最优情况是：O(nlogn)）。

出现次数超过一半的那个数，我们怎么在O(n)时间复杂度内把它揪出来，我教你：大浪淘沙法，是金子总会发光法，我要打十个法（意思就是，这一个数就能干翻全场剩下的所有数，是不是？因为它超过一半啊）。我们来想象一下：我们遍历这个数组的时候，定义一个count用来计数，这个超过一半的数，它遇到自己就给count加1，遇到不是自己的数，就给count减1，最后会怎样呢，count肯定大于0呐，因为这个数的个数超过一半。好，进一步的，我们先随便找个数当这个老大（个数超过一半），如果它的个数不超过一半，就会在相消中时count为0，那么就把它换掉，最后剩下的那个就是，个数超过一半的那个数了。

代码如下：

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = 1
        n = nums[0]
        for x in range(1, len(nums)):
            if count == 0:
                n = nums[x]
                count += 1
            else:
                if nums[x] == n:
                    count += 1
                else:
                    count -= 1
        return n

超过一半呐，多么重的一条信息，稍微想想就知道，用相消法都能消出那个数，跟那个用异或消出只出现一次的数（其它的数都是成对的，就是都恰好有两个）是不是异曲同工呐，嗯还是扯得有点远。

另外这个题在leetcode上的难度是easy哦，好伤心啊，当初的我连这题都没想出解法，真是够年轻啊。

私有云云服务器 Majority 169邮箱 169短信群发 Element

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/38353.html

LeetCode[169] Majority Element

摘要：投票法复杂度思路设定一个和这个对应的如果一个数和这个相等，那么就将增加，否则减少的数目。 LeetCode[169] Majority Element Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2...

int64 2019-08-14 15:01 评论0 收藏0
LeetCode 之 JavaScript 解答第169题 —— 求众数 I（Majority El

摘要：小鹿题目算法思路摩尔投票算法题目的要求是让我们求数组中超过一半数据以上相同的元素且总是存在的。 Time：2019/4/4Title: Majority Element 1Difficulty: easyAuthor: 小鹿题目：Majority Element 1 Given an array of size n, find the majority element. The ...

hightopo 2019-08-23 16:45 评论0 收藏0
Leetcode PHP题解--D83 169. Majority Element

摘要：题目链接题目分析给定一个数组，返回其中出现次数超过一半的元素。思路用函数计算元素出现次数，用逆序排序结果，输出第一个即可。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D83 169. Majority Element 题目链接 169. Majority Element 题目分析给定一个数组，返回其中出现次数超过一半的元素。思路用array_count_values函数计算...

yagami 2019-07-01 13:57 评论0 收藏0
leetcode 169 Majority Element

摘要：因为众数出现的次数必定大于，所以我们只要取第个位置上的元素，这个元素一定为我们要找的众数。题目详情 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 th...

tangr206 2019-08-15 13:53 评论0 收藏0
Majority Vote Alogrithm（最大投票算法）及其扩展

摘要：，这是最基础的最大投票算法。例如，和这两个数组最后得到的分别为和，但是这并不影响答案的正确性。接下来，我们可以对这个算法做一些简单的扩展，我们当前定义的的数量大于的元素。为当前出现的次数。这意味着当前这个数字就是这两个等待的第三个数字。 Boyer-Moore：A Linear Time Majority Vote Alogrithm，这是最基础的最大投票算法。原文中提到：decid...

niceforbear 2019-08-14 15:25 评论0 收藏0