[分析] Majority Element II这个扩展版可以沿用Majority Element 中的Moore Voting解法,大于 N / 3最多有两个,遍历过程中记录两个候选值。需注意的是,遍历结束后的候选值并不一定符合条件,比如input= [1,1,2],因此需要个检查过程。
[ref]
对Moore Voting算法解析
http://blog.csdn.net/joylnwang/article/details/7081575
public class Solution {
public List<Integer> majorityElement(int[] nums) {
// Moore voting
List<Integer> result = new ArrayList<Integer>();
if (nums == null || nums.length == 0) return result;
int N = nums.length;
int cand1 = nums[0], counter1 = 1;
int i = 1;
while (i < N && cand1 == nums[i]) {
counter1++;
i++;
}
if (i == N) {
result.add(cand1);
return result;
}
int cand2 = nums[i++], counter2 = 1;
while (i < N) {
if (nums[i] == cand1) {
cand1 = nums[i];
counter1++;
} else if (nums[i] == cand2) {
cand2 = nums[i];
counter2++;
} else {
if (counter1 == 0) {
cand1 = nums[i];
counter1++;
} else if (counter2 == 0) {
cand2 = nums[i];
counter2++;
} else {
counter1--;
counter2--;
}
}
i++;
}
// check cand1 & cand2
int c1 = 0, c2 = 0;
for (int j = 0; j < N; j++) {
if (cand1 == nums[j])
c1++;
else if (cand2 == nums[j])
c2++;
}
if (c1 > N / 3)
result.add(cand1);
if (c2 > N / 3)
result.add(cand2);
return result;
}
}
分享到:
相关推荐
c c语言_leetcode题解之0229_majority_element_ii
python python_leetcode题解之229_Majority_Element_II.py
Element”的解决方案。 注意力! 因为我直接在leetcode Judge web里面写代码,所以很多getSolution()没有测试用例。 如果您想在Xcode中进行测试,请自行添加测试用例! 每个问题的结构如下: struct q169 { class ...
leetcode category other hot keywords:Palindrome(mic), Subsequence Array 螺旋矩阵Spiral Matrix 顺时针打印矩阵 Next Permutation Product of Array Except Self 189.rotate-array 283.move-zero Range Sum ...
Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate ...
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-...
6. **统计问题**:如“数组中出现次数超过一半的数字”(Majority Element),使用Boyer-Moore投票算法结合哈希表,可以在O(n)时间内找到数组中出现次数超过一半的元素。 7. **查找重复元素**:“数组中的重复元素...
圆和椭圆重叠leetcode ——#158 尖端 关心特殊情况 从不同的方向思考 简单的 大批 1.Two Sum -> 使用哈希表避免遍历列表448.查找数组中消失的所有数字-> 1.建立缓冲区来计算数字| 2.使用数组作为带符号的缓冲区118....
leetcode有效期 algorithmTask 数据结构与算法练习 ...英文版:https://leetcode.com/problems/majority-element/ 中文版:https://leetcode-cn.com/problems/majority-element/ Missing Positive(求缺失
137 | [Single Number II](https://leetcode.com/problems/single-number-ii/) | [C++](./C++/single-number-ii.cpp) [Python](./Python/single-number-ii.py) | _O(n)_ | _O(1)_ | Medium ||| 190 | [Reverse Bits]...
Element II 解决方法:Majority Voting算法的变种。但是最终的算法实现形式,很难理解。 2018-08-19 19:16 LeetCode: 79. Word Search 解决方法:DFS LeetCode: 31. Next Permutation 解决方法:掌握排列组合的字典...
java lru leetcode leetcode_java Java版中的解决方案。 Dectinc_Chen 解决问题清单 已解决问题列表 [除Self之外的数组乘积](md/除Self.md之外的数组...II](md/Majority Element II.md) - 2015-09-22 [摘要范围](md/Sum
leetcode中国 Leetcode Set Matrix Zeroes 第一种 通过一次遍历记录所有为0的索引(Python中enumerate()输出当前列表的索引) 再遍历一次, 根据记录的索引进行置0 第二种 ...Majority Element 多数投票算法
leetcode有效期 Datawhale-Coding ...Element(求众数) 英文版: 中文版: Missing Positive(求缺失的第一个正数)[作为可选] 英文版: 中文版: Linked List Cycle I(环形链表) 英文版: 中文版: Merge k
leetcode卡 Programming 课程设计:光城 、LeoLRH 组队学习说明:利用自己所熟知的编程语言,具有一定基础,讨论在面试中可能出现的数据结构问题,一起学习重温经典数据结构 ...Element(求众数) Missi
加油站 ...229_Majority_Element_II 274_H_索引 275_H_Index_II 217_Contain_Duplicate 55_Jump_Game 45_Jump_Game_II 121_Best_Time_to_Buy_and_Sell_Stock 122_Best_Time_to_Buy_and_Sell_Stock_
2. **统计元素出现次数**:如“出现次数超过一半的数字”(Majority Element),哈希表可以用来统计每个元素出现的频率,找出出现次数超过一半的元素。 3. **子集或子串查找**:“无重复字符的最长子串”(Longest ...
[C ++](./ Algorithms / Majority Element II / Source.cpp) 中等的 2015年7月4日 228 [C ++](./算法/摘要范围/Source.cpp) 简单的 2015年7月1日 227 [C ++](./ Algorithms / Basic Calculator II / Sour
leetcode 2 sum c DataWhale_exercise programming in ...Element(求众数) 英文版: 中文版: Missing Positive(求缺失的第一个正数)[作为可选] 英文版: 中文版: Linked List Cycle I(环形链
majority element ii . 使用 "摩尔投票法"。 LCA 二叉树最近共同祖先问题. 递归结题的思路,在左子树、右子树查找两个节点,可能的结果有: 该节点就是其中的一个节点,则返回该节点 两个节点都不在左边,那么肯定都...