- 浏览: 174331 次
- 性别:
- 来自: 济南
文章分类
最新评论
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.
从数组中找到出现次数多于一般的元素。题目中有两个限定条件,一个是非空,另一个是肯定有一个元素出现次数多余一半。这种情况下我们可以用Moore voting algorithm。每找出两个不同的元素,成对的删除,最终剩下的一定就是出现次数最多的。时间复杂度为O(n)。代码如下:
You may assume that the array is non-empty and the majority element always exist in the array.
从数组中找到出现次数多于一般的元素。题目中有两个限定条件,一个是非空,另一个是肯定有一个元素出现次数多余一半。这种情况下我们可以用Moore voting algorithm。每找出两个不同的元素,成对的删除,最终剩下的一定就是出现次数最多的。时间复杂度为O(n)。代码如下:
public class Solution { public int majorityElement(int[] nums) { int count = 0; int current = 0; for(int i : nums) { if(count == 0) { current = i; count ++; } else if(current == i) { count ++; } else { count --; } } return current; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 229Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 231You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 347Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 339Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 458Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 524Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 434Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 623Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 434The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 392Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 522Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 540Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 376All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 868Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 884Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 559Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 604Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 770Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 741You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 635For a undirected graph with tre ...
相关推荐
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-...
Majority Element Rotate Array Contains Duplicate Contains Duplicate II Contains Duplicate III Product of Array Except Self Game of Life Increasing Triplet Subsequence 单链表 Reverse Linked List Odd ...
27 | [Remove Element](https://leetcode.com/problems/remove-element/) | [C++](./C++/remove-element.cpp) [Python](./Python/remove-element.py) | _O(n)_ | _O(1)_ | Easy || 31 | [Next Permutation]...
leetcode有效期 algorithmTask 数据结构与算法练习 Task.1 数组 实现一个支持动态扩容的数组,支持增删改操作 ...中文版:https://leetcode-cn.com/problems/majority-element/ Missing Positive(求缺失
java lru leetcode leetcode_java Java版中的解决方案。 Dectinc_Chen 解决问题清单 已解决问题列表 [除Self之外的数组乘积](md/除Self.md之外的数组...II](md/Majority Element II.md) - 2015-09-22 [摘要范围](md/Sum
Find a majority element in an array of size 'n'3. Find the number occuring odd number of times in a given array of size 'n'4. Algorithm to reverse an array5. Algorithm to rotate array of size 'n' by ...
Majority Element LCCI Game of Life Find All Numbers Disappeared in an Array Shortest Unsorted Continuous Subarray Rotate Image 宝石与石头Jewels and Stones Kids With the Greatest Number of Candies 美团...
#169 Majority Element #171 Excel Sheet Column Number #217 Contains Duplicate #226 Invert Binary Tree #237 Delete Node in a Linked List #238 Product of Array Except Self #242 Valid Anagram #258 Add ...
Element II 解决方法:Majority Voting算法的变种。但是最终的算法实现形式,很难理解。 2018-08-19 19:16 LeetCode: 79. Word Search 解决方法:DFS LeetCode: 31. Next Permutation 解决方法:掌握排列组合的字典...
[C ++](./ Algorithms / Majority Element II / Source.cpp) 中等的 2015年7月4日 228 [C ++](./算法/摘要范围/Source.cpp) 简单的 2015年7月1日 227 [C ++](./ Algorithms / Basic Calculator II / Sour
majority element ii . 使用 "摩尔投票法"。 LCA 二叉树最近共同祖先问题. 递归结题的思路,在左子树、右子树查找两个节点,可能的结果有: 该节点就是其中的一个节点,则返回该节点 两个节点都不在左边,那么肯定都...
圆和椭圆重叠leetcode ——#158 尖端 关心特殊情况 ...是一个常数,所以可以计算出缺失的那个169.Majority Element -> Hashtable | Boyer-Moore 多数投票算法283. 移零 -> 27. 移除元素243.Shortest Word Dista
Element”的解决方案。 注意力! 因为我直接在leetcode Judge web里面写代码,所以很多getSolution()没有测试用例。 如果您想在Xcode中进行测试,请自行添加测试用例! 每个问题的结构如下: struct q169 { class ...
leetcode添加元素使和等于 本项目为Njueers所共享 仓库内容主要为平时刷题的submit、遇到的...Majority Element II,类似求一个数组中,超过一定重复次数的数,可以考虑摩尔投票算法 2019/07/17 新增 307. Range Sum Que
leetcode 2 sum c DataWhale_exercise programming in ...Element(求众数) 英文版: 中文版: Missing Positive(求缺失的第一个正数)[作为可选] 英文版: 中文版: Linked List Cycle I(环形链
Element(求众数) 英文版: 中文版: Missing Positive(求缺失的第一个正数) 英文版: 中文版: Linked List Cycle I(环形链表) 英文版: 中文版: Merge k Sorted Lists(合并 k 个排序链表) 英文版: 中文版...
valid number leetcode ...Element(求众数) 英文版: 中文版: Missing Positive(求缺失的第一个正数)[作为可选] 英文版: 中文版: Linked List Cycle I(环形链表) 英文版: 中文版: Merge k
valid number leetcode 自动机 ...Element(求众数) 英文版: 中文版: Missing Positive(求缺失的第一个正数)[作为可选] 英文版: 中文版: Linked List Cycle I(环形链表) 英文版: 中文版: Me
leetcode有效期 Datawhale-Coding ...Element(求众数) 英文版: 中文版: Missing Positive(求缺失的第一个正数)[作为可选] 英文版: 中文版: Linked List Cycle I(环形链表) 英文版: 中文版: Merge k
leetcode中国 Leetcode Set Matrix Zeroes 第一种 通过一次遍历记录所有为0的索引(Python中enumerate()输出当前列表的索引) 再遍历一次, 根据记录的索引进行置0 第二种 ...Majority Element 多数投票算法