找寻多数元素

r囧r小猫 2022-10-05 04:45 109阅读 0赞

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。  
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：
    
    输入：[3,2,3]
    输出：3
    示例 2：
    
    输入：[2,2,1,1,1,2,2]
    输出：2

思路：1哈希表  
1、统计出每个元素出现的次数  
2、遍历找出元素最多的

class Solution {
        
        private Map<Integer, Integer> countNums(int[] nums) {
        
            Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
            for (int num : nums) {
        
                if (!counts.containsKey(num)) {
        
                    counts.put(num, 1);
                } else {
        
                    counts.put(num, counts.get(num) + 1);
                }
            }
            return counts;
        }
    
        public int majorityElement(int[] nums) {
        
            Map<Integer, Integer> counts = countNums(nums);
    
            Map.Entry<Integer, Integer> majorityEntry = null;
            for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
        
                if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
        
                    majorityEntry = entry;
                }
            }
    
            return majorityEntry.getKey();
        }
    }

思路2：  
如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 \\lfloor \\dfrac\{n\}\{2\} \\rfloor⌊  
2  
n  
  
⌋ 的元素（下标从 0 开始）一定是众数。

在class Solution {
        
        public int majorityElement(int[] nums) {
        
            Arrays.sort(nums);//数组排序
            return nums[nums.length / 2];
        }
    }

思路3：分治算法待补充

发表评论取消回复

表情：

评论列表（有 0 条评论，109人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode169. 多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。示例

逃离我推掉我的手/ 2023年06月22日 13:46/ 0 赞/ 152 阅读

相关 02_多数元素(Python)

目录多数元素示例 1：示例 2：进阶：解答 1，先排序 2，使用Map解决 3，位运算解决

布满荆棘的人生/ 2023年01月13日 05:52/ 0 赞/ 86 阅读

相关【LeetCode 169】多数元素

题目描述给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数

约定不等于承诺〃/ 2022年12月01日 05:10/ 0 赞/ 141 阅读

相关数组----169. 多数元素

/ 169. 多数元素给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并

超、凢脫俗/ 2022年11月19日 01:14/ 0 赞/ 153 阅读

相关找寻多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

r囧r小猫/ 2022年10月05日 04:45/ 0 赞/ 110 阅读

相关 169. 多数元素

[https://leetcode-cn.com/problems/majority-element/][https_leetcode-cn.com_problems_majo

痛定思痛。/ 2022年09月10日 13:26/ 0 赞/ 168 阅读

相关 leetcode169多数元素

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

￡神魔★判官ぃ/ 2022年09月05日 00:12/ 0 赞/ 154 阅读

相关力扣多数元素

169. 多数元素给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 `⌊ n/2 ⌋` 的元素。你可以假设数组是非空的，并且给定的

蔚落/ 2022年08月28日 11:00/ 0 赞/ 151 阅读

相关多数元素

//给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 // // 你可以假设数组是非空的，并且给定的数组总是存

曾经终败给现在/ 2021年06月22日 15:38/ 0 赞/ 435 阅读

相关【LeetCode】 169. 多数元素

<table> <tbody> <tr> <td><font>题目</font></td> </tr> </tbody> </table>

小咪咪/ 2021年06月10日 20:38/ 0 赞/ 435 阅读