首页 > 试题广场 >

数组中出现次数超过一半的数字

[编程题]数组中出现次数超过一半的数字
  • 热度指数：862679 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围：，数组中元素的值
要求：空间复杂度：，时间复杂度

输入描述:
保证数组输入非空，且保证有解

示例1

输入

[1,2,3,2,2,2,5,4,2]

输出

2
示例2

输入

[3,3,3,3,2,2,2]

输出

3
示例3

输入

[1]

输出

1
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-01 14:34:21
精华题解 描述 这是一篇针对初学者的题解。共用三种方法解决。知识点：数组，排序，哈希难度：一星 题解 题目抽象：给定一个数组，找出数组中的众数，若有，返回众数，若没有，返回0众数定义：数组中出现次数大于数组一般的元素 方法一：哈希法 根据题目意思，显然可以先遍历一遍数组，在map中存每个元素出现的次数，然后 展开全文
去ta的博客 赞 (172) 回复(18) 收起
头像 蒙牛麦片
发表于 2021-06-24 09:50:59
精华题解 JZ28 数组中出现次数超过一半的数字 题意分析 找出数组中出现次数大于数组长度一半的数字。 示例输入：input = [1,2,3,2,2,2,5,4,2]返回：2解释：在input数组中，数组的长度为9,数字2出现的次数为5，大于。因此返回值为2； 题解一（数字统计）： 我们对给定的数组进行数字 展开全文
去ta的博客 赞 (24) 回复(8) 收起
头像 Maokt
发表于 2021-07-19 13:47:36
精华题解 算法思想一：哈希表 解题思路： 出现次数最多的元素大于 n/2 次，所以可以用哈希表来快速统计每个元素出现的次数 1、使用哈希映射来存储每个元素以及出现的次数。对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数。 2、用一个循环遍历数组 nums 并将数组中的每 展开全文
去ta的博客 赞 (10) 回复(2) 收起
头像 leaves0924
发表于 2021-06-23 13:08:32
精华题解 题目描述 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。你可以假设数组是非空的，并且给定的数组总是存在多数元素。1<=数组长度<=50000示例 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 牛客题解官
发表于 2022-04-22 12:22:36
精华题解 题目主要信息: 题目给出一个长度为n的数组，其中有一个数字出现次数超过了数组长度的一半，需要我们找出这个数字 输入数组非空，保证有解，这样就不用考虑特殊情况 举一反三： 学习完本题的思路你可以解决如下题目： BM52. 数组中只出现一次的两个数字 BM53. 缺失的第一个正整数 方法：哈希表（推 展开全文
去ta的博客 赞 (5) 回复(2) 收起
头像 GhostLX
发表于 2021-07-21 17:21:00
精华题解 算法一：哈希映射 算法思路 开一个map容器或者是unordered_map容器来记录一个数出现的次数，最后在逐个访问容器中的元素，找到比大的那个就行了复杂度分析 值得注意的是map和unordered_map内嵌数据结构是不同的，map是红黑树，unordered_map是哈希表使用map 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Peterliang
发表于 2021-06-23 10:57:53
精华题解 题意分析 给出一个数组，我们需要找出在这个数组里面出现的次数超过这个数组长度的一半的那个数字。 思路分析 思路一 由于需要我们求出众数，那么我们可以尝试着先进行排序，然后我们只需要遍历排好序的数组就行了，这种情况下排序的时间复杂度是,但是我们遍历的时候如果最好只要n/2+1就行，最差就是n。由 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 幸福的火龙果在干饭
发表于 2021-06-28 20:07:52
精华题解 一、题目描述 JZ28 数组中出现次数超过一半的数字题目大意：数组中有一个数字出现的次数超过数组长度的一半, 找出这个数字注意审题：假设数组是非空的, 故给定的数组中有且只有一个满足条件的数 二、算法1（排序） 解题思路 我们知道, 对一个数组进行排序之后, 则相同的元素一定是连续的, 因此, 我 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 2019113913
发表于 2021-07-18 01:05:42
精华题解 题意思路：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。你可以假设数组是非空的，并且给定的数组总是存在多数元素。1<=数组长度<=50000 方 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 一叶浮尘
发表于 2019-08-17 20:23:27
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。思路：用一般的排序也可以完成这道题目，但是如果那样完成的话就可能太简单了。用preValu 展开全文
去ta的博客 赞 (84) 回复(18) 收起
头像 没有人比我更菜
发表于 2019-12-06 22:47:31
这道题，最直白的解法是使用一个 map 来记录各个数字出现的次数，最后取出现次数最多的作为解。但这个方法需要消耗额外的空间，不是最优。下面是最优解法： 我们做这样的想象，现在有来自不同阵营的多支部队，他们互为敌人。每个士兵都容不得敌人，宁愿与敌人同归于尽。可以想象，如果某个阵营的士兵数量超过所有阵营 展开全文
去ta的博客 赞 (69) 回复(13) 收起
头像 一颗闪闪发亮的马路星
发表于 2020-02-11 00:10:20
题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。这题我看很多大佬给出了很精简的答案，有的只有好几行，我觉得很厉害，但是对小白或者初 展开全文
去ta的博客 赞 (33) 回复(1) 收起
头像 MemoryC
发表于 2019-09-22 21:10:51
三行代码搞定数组中出现次数超过一半的数字 <center>普林斯MemoryC</center> 题目 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组 展开全文
去ta的博客 赞 (29) 回复(6) 收起
头像 不是江小白
发表于 2021-08-12 21:49:09
1. 解题思路之 了解暴力法 题目的描述这句话（“例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。”）其实就已经给出了思路。就是👉暴力解法： 首先找到数组长度的一半，这里为 ， 定为 n 变量； 接着统计数组中各 展开全文
去ta的博客 赞 (17) 回复(0) 收起
头像 Black-K
发表于 2021-08-05 23:31:24
两行代码搞定。。。。 class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { sort(numbers.begin(),numbers.end()); ret 展开全文
去ta的博客 赞 (9) 回复(2) 收起
头像 勇敢牛牛不怕困难～
发表于 2020-11-15 11:08:26
public class Solution {     public int MoreThanHalfNum_Solution(int [] array) {  &nbs 展开全文
去ta的博客 赞 (8) 回复(2) 收起
头像 郭家兴0624
发表于 2019-08-10 22:32:53
题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。 思路1：对数组排序，找数组中间的数。 def MoreThanHalfNum_S 展开全文
去ta的博客 赞 (8) 回复(2) 收起
头像 宫水三叶的刷题日记
发表于 2021-07-26 17:39:58
基本分析 为了让解法更具有「通用性」，我们可以考虑添加一个额外条件：数组中不一定存在「出现次数超过一半的数字」，如果不存在的话返回 。 这也是在面试过程中，很容易被拓展的一个点。 哈希表 一个朴素的做法是使用哈希表进行计数，如果发现某个元素数量超过总数一半，说明找到了答案。 代码： import 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 学无止境呀～
发表于 2019-09-06 10:52:45
28. 数组中出现次数超过一半的数字 题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。 思路思路1：遍历数组，用字典dict存储 展开全文
去ta的博客 赞 (7) 回复(1) 收起

问题信息

数组 哈希
难度：
2290条回答 187589浏览

热门推荐

通过挑战的用户

查看代码

相关试题

数组中出现次数超过一半的数字

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号