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.
public class Solution { public List<Integer> majorityElement(int[] nums) { List<Integer> res = new ArrayList<>(); printKMajor(nums, 3, res); return res; } private void printKMajor(int[] nums, int k, List<Integer> res) { // TODO Auto-generated method stub if (k < 2) { return; } HashMap<Integer,Integer> cands = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (cands.containsKey(nums[i])) { cands.put(nums[i], cands.get(nums[i]) + 1); } else { if (cands.size() == k - 1) { allCandsNinusOne(cands); } else { cands.put(nums[i], 1); } } } HashMap<Integer,Integer> reals = getReals(nums, cands); for (Map.Entry<Integer, Integer> set : reals.entrySet()) { Integer key = set.getKey(); if (reals.get(key) > nums.length / k) { res.add(key); } } } private HashMap<Integer,Integer> getReals(int[] nums, HashMap<Integer, Integer> cands) { // TODO Auto-generated method stub HashMap<Integer,Integer> hashMap = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int num = nums[i]; if (cands.containsKey(num)) { if (hashMap.containsKey(num)) { hashMap.put(num, hashMap.get(num) + 1); } else { hashMap.put(num, 1); } } } return hashMap; } private void allCandsNinusOne(HashMap<Integer, Integer> map) { // TODO Auto-generated method stub LinkedList<Integer> linkedList = new LinkedList<>(); for (Map.Entry<Integer, Integer> set : map.entrySet()) { Integer key = set.getKey(); Integer value = set.getValue(); if (value == 1) { linkedList.add(key); } map.put(key, value - 1); } for (Integer integer : linkedList) { map.remove(integer); } } }
相关推荐
在解决算法问题时,使用Python编程语言解决LeetCode上的“Majority Element II”问题是一次有趣且富有挑战性的经历。这个问题要求编写一个函数,找出数组中出现次数超过 ⌊ n/3 ⌋ 的元素。为了达到这个目标,我们...
c c语言_leetcode题解之0229_majority_element_ii
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-...
在LeetCode算法题库中,“Online Majority Element In Subarray”是一道涉及数据流处理和查找算法的问题。该问题的大致内容是设计一个数据结构,用于处理一个数据流,这个数据结构能够快速查询给定子区间内出现次数...
针对"majority-element"问题的js-leetcode题解之169-majority-element.js,开发者们通常会利用摩尔投票算法(Moore Voting Algorithm)来寻找多数元素,这是一个时间复杂度为O(n)、空间复杂度为O(1)的高效解决方案。...
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
def majorityElementII(nums): table = {} for i, num in enumerate(nums): if num not in table: table[num] = 1 else: table[num] += 1 for key, value in table.items(): if value > len(nums) // 3: ...
在编程领域,寻找多数元素(Majority Element)是一项常见的任务,尤其在算法设计和数据处理中。多数元素指的是在一个整数数组中出现次数超过数组长度一半的元素。本主题将详细探讨如何用C++语言来解决这个问题。 ...
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