2019-03-11-算法-进化（求众数）

旧城等待， 2022-03-10 16:54 174阅读 0赞

**题目描述**  
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

**示例 1:**

输入: [3,2,3]
    输出: 3

**示例 2:**

输入: [2,2,1,1,1,2,2]
    输出: 2

思路：

1.  数组先排序，然后取length/2的元素。时间复杂度：O(nlog(n))，空间复杂度O(1)
2.  摩尔投票法。时间复杂度：O(n)，空间复杂度O(1)
3.  使用Map保存每个元素的计数，然后遍历Map取计数最大值。时间复杂度：O(nlog(n))，空间复杂度O(n)

**思路1**实现代码：

public int majorityElement(int[] nums) {
    		Arrays.sort(nums);
    		return nums[nums.length/2];
        }

**思路2**，摩尔投票法是统计占多数票的算法。  
![摩尔投票法][20190311164953209.png]  
参考博客：[https://blog.csdn.net/tfcy694/article/details/82717808][https_blog.csdn.net_tfcy694_article_details_82717808]  
对应实现代码如下：

/**
    	 * 摩尔投票算法
    	 * @param nums
    	 * @return
    	 */
    	public int majorityElement(int[] nums) {
    		int res = nums[0];
    		int count=1;
    		for(int i=1;i<nums.length;i++) {
    			if(res == nums[i]) {
    				count++;
    			}else {
    				count--;
    				if(count ==0) {
    					res=nums[i];
    					count=1;
    				}
    			}
    		}
    		return res;
        }

**思路3**也很简单，代码就不贴出来了

[20190311164953209.png]: /images/20220310/56257410b9654ba2ac4b50cccdc8790a.png
[https_blog.csdn.net_tfcy694_article_details_82717808]: https://blog.csdn.net/tfcy694/article/details/82717808

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode-求众数

LeetCode-求众数题目给定一个大小为 *n* 的数组，找到其中的众数。众数是指在数组中出现次数**大于** `⌊ n/2 ⌋` 的元素。你可以假设...

太过爱你忘了你带给我的痛/ 2024年04月17日 05:58/ 0 赞/ 87 阅读

相关 LeetCode 求众数

题目链接：[https://leetcode-cn.com/problems/majority-element/][https_leetcode-cn.com_problems

朴灿烈づ我的快乐病毒、/ 2023年06月04日 14:56/ 0 赞/ 25 阅读

相关 go求众数

求众数，其中有两种方法： 1. 声明一个map，将遍历的到的数字作为索引，在map中进行+1，最后判断哪个索引对应的数字大于数组长度的一半，则返回索引。 func

旧城等待，/ 2022年12月25日 05:00/ 0 赞/ 174 阅读

相关算法题目——求众数

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

╰+攻爆jí腚メ/ 2022年09月14日 08:55/ 0 赞/ 201 阅读

相关 leetcode 求众数

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

àì夳堔傛蜴生んèń/ 2022年04月23日 09:48/ 0 赞/ 245 阅读

相关 2019-03-11-算法-进化（求众数）

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

旧城等待，/ 2022年03月10日 16:54/ 0 赞/ 175 阅读

相关 leetcode-求众数

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

你的名字/ 2021年12月24日 00:53/ 0 赞/ 331 阅读

相关 LeetCode----------------------求众数

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

绝地灬酷狼/ 2021年12月10日 12:19/ 0 赞/ 273 阅读

相关算法面试题汇总_2求众数

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

Love The Way You Lie/ 2021年12月10日 07:25/ 0 赞/ 271 阅读

相关 leetcode 求众数

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

我不是女神ヾ/ 2021年11月02日 09:18/ 0 赞/ 397 阅读