- 浏览: 173701 次
- 性别:
- 来自: 济南
文章分类
最新评论
Majority Element
给定一个长度为n的数组,从中找出出现次数最多的元素,这个元素出现的次数多余[n/2]次。假设数组不为空并且始终存在一个majority元素。
解决这道题有很多种方法,但是时间复杂度和空间复杂度各不相同,在这里我们用三种不同的方法解这道题。
1,最简单的方法就是先将数组排好序,根据题意我们知道,出现最多的元素肯定是中间的元素。
我们直接调用Arrays的sort方法,这样时间复杂度是O(nlogn),空间复杂度为O(1)。代码如下:
2,第二种方法我们可以用哈希表来记录元素出现的次数,直到找到一个元素出现次数多于数组长度的一半就返回。这样空间复杂度为O(n),时间复杂度为O(n)。相当于用空间换时间,实现代码如下:
3,这是一个很巧妙的算法,叫做Moore Voting Algorithm。它专门用来处理出现次数最多元素的,它的时间复杂度为O(n),空间复杂度为O(1)。它的思想是在数组中找成对的元素,如果它们的值不相等,就忽略它们,相当于把它们删除;如果它们的值相等,那么就用一个变量来记录重复的次数。通过代码来理解更直观,代码如下:
给定一个长度为n的数组,从中找出出现次数最多的元素,这个元素出现的次数多余[n/2]次。假设数组不为空并且始终存在一个majority元素。
解决这道题有很多种方法,但是时间复杂度和空间复杂度各不相同,在这里我们用三种不同的方法解这道题。
1,最简单的方法就是先将数组排好序,根据题意我们知道,出现最多的元素肯定是中间的元素。
我们直接调用Arrays的sort方法,这样时间复杂度是O(nlogn),空间复杂度为O(1)。代码如下:
public class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); if(nums.length==1) { return nums[0]; } else { return nums[nums.length / 2]; } } }
2,第二种方法我们可以用哈希表来记录元素出现的次数,直到找到一个元素出现次数多于数组长度的一半就返回。这样空间复杂度为O(n),时间复杂度为O(n)。相当于用空间换时间,实现代码如下:
public class Solution { public int majorityElement(int[] nums) { HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>(); int result = 0; for(int i = 0; i < nums.length; i++) { if(hm.containsKey(nums[i])) { hm.put(nums[i], hm.get(nums[i])+1); } else { hm.put(nums[i], 1); } if(hm.get(nums[i]) > nums.length/2) { result = nums[i]; break; } } return result; } }
3,这是一个很巧妙的算法,叫做Moore Voting Algorithm。它专门用来处理出现次数最多元素的,它的时间复杂度为O(n),空间复杂度为O(1)。它的思想是在数组中找成对的元素,如果它们的值不相等,就忽略它们,相当于把它们删除;如果它们的值相等,那么就用一个变量来记录重复的次数。通过代码来理解更直观,代码如下:
public class Solution { public int majorityElement(int[] nums) { int count = 0; int result = 0; for(int num : nums) { if(count == 0) result = num; if(result != num) { count --; } else { count ++; } } return result; } }
发表评论
-
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 228You 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 335Given 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 513Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 431Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 622Follow 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 388Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 519Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 534Given 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 862Given 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 736You 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-...
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 多数投票算法