LeetCode[169] Majority Element

int64 发布于2019-08-14 15:01 / 3127人阅读

摘要：投票法复杂度思路设定一个和这个对应的如果一个数和这个相等，那么就将增加，否则减少的数目。

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 that the array is non-empty and the majority element always exist in the array.

投票法

复杂度
O(N),O(1)

思路
设定一个candidate,和这个candidate对应的count.如果一个数和这个candidate相等，那么就将count增加，否则减少count的数目。

代码

public int majorityElement(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    int candidate = 0;
    int cnt = 0;
    for(int num : nums) {
        if(num == candidate) {
            cnt ++;
        }
        else if(cnt == 0) {
            candidate = num;
        }
        else {
            cnt --;
        }
    }
    return candidate;
}

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

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

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

leetcode讲解--169. Majority Element

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

LiuRhoRamen 2019-07-25 11:21 评论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