- 浏览: 173366 次
- 性别:
- 来自: 济南
文章分类
最新评论
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
这道题目是Majority Element的变形,这里要求找出出现次数多余n/3次。我们通过分析可以知道这样的元素可能有两个,我们同样可以采用Moore算法,与上一题目不同的的是三个元素一组,这样在线性的时间复杂度下可以解决。代码如下:
这道题目是Majority Element的变形,这里要求找出出现次数多余n/3次。我们通过分析可以知道这样的元素可能有两个,我们同样可以采用Moore算法,与上一题目不同的的是三个元素一组,这样在线性的时间复杂度下可以解决。代码如下:
public class Solution { public List<Integer> majorityElement(int[] nums) { List<Integer> list = new ArrayList<Integer>(); int result1 = 0; int result2 = 0; int count1 = 0, count2 = 0; for(int i : nums) { if(count1 == 0 && i != result2) { result1 = i; } else if(count2 == 0 && i != result1) { result2 = i; } if(i == result1) { count1 ++; } else if(i == result2) { count2 ++; } else { count1 --; count2 --; } } count1 = 0; count2 = 0; for(int i : nums) { if(i == result1) count1 ++; else if(i == result2) count2 ++; } if(count1 > nums.length / 3) list.add(result1); if(count2 > nums.length / 3) list.add(result2); return list; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 227Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 226You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 342Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 333Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 451Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 511Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 430Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 619Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 428The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 387Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 517Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 531Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 371All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 861Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 883Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 555Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 601Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 764Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 735You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 629For 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-...
java lru leetcode leetcode_java Java版中的解决方案。 Dectinc_Chen 解决问题清单 已解决问题列表 [除Self之外的数组乘积](md/除Self.md之外的数组...II](md/Majority Element II.md) - 2015-09-22 [摘要范围](md/Sum
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]...
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添加元素使和等于 本项目为Njueers所共享 仓库内容主要为平时刷题的submit、遇到的...Majority Element II,类似求一个数组中,超过一定重复次数的数,可以考虑摩尔投票算法 2019/07/17 新增 307. Range Sum Que
leetcode有效期 algorithmTask 数据结构与算法练习 Task.1 数组 实现一个支持动态扩容的数组,支持增删改操作 ...中文版:https://leetcode-cn.com/problems/majority-element/ Missing Positive(求缺失
加油站 ...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_
#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 ...
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 美团...
圆和椭圆重叠leetcode ——#158 尖端 关心特殊情况 ...是一个常数,所以可以计算出缺失的那个169.Majority Element -> Hashtable | Boyer-Moore 多数投票算法283. 移零 -> 27. 移除元素243.Shortest Word Dista
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 ...
Element”的解决方案。 注意力! 因为我直接在leetcode Judge web里面写代码,所以很多getSolution()没有测试用例。 如果您想在Xcode中进行测试,请自行添加测试用例! 每个问题的结构如下: struct q169 { class ...
leetcode中国 Leetcode Set Matrix Zeroes 第一种 通过一次遍历记录所有为0的索引(Python中enumerate()输出当前列表的索引) 再遍历一次, 根据记录的索引进行置0 第二种 ...Majority Element 多数投票算法
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