【LeetCode & 剑指offer刷题】数组题7：39 数组中出现次数超过一半的数字

谁践踏了优雅 2021-10-01 07:00 157阅读 0赞

**[【LeetCode & 剑指offer 刷题笔记】目录（持续更新中...）][LeetCode _ _offer _...]**

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

## **题目描述** ##

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

\#include <unordered\_map> // 用 hash 表实现

**using** **namespace** std **;**

//方法一：hash 表实现， O （ n ） ,O(n)

class Solution

**\{**

public **:**

int MoreThanHalfNum\_Solution **(** vector **<** int **>** numbers **)**

**\{**

unordered\_map **<** int **,** int **>** counter **;**

int k **=** numbers **.** size **()** **/** 2 **;**

**for** **(** int ai **:** numbers **)** // 遍历数组 O(n)

**\{**

counter **\[** ai **\]++;** // 构建计数器

**if** **(** counter **\[** ai **\]** **>** k **)** **return** ai **;** // 节省时间

**\}**

//   for(auto& n:counter) // 遍历计数器 O(k) , 这里为 map 中的引用，不是指针，故直接用 n.first

// \{

//   if(n.second > k)

// \{

//      return n.first;

//   \}

// \}

**return** 0 **;** // 不存在

**\}**

**\};**

/\*

方法二：“消解法”：如果一个数出现次数超过数组的一半，则其出现的次数比其他所有数字出现次数的和还要多，可以用两不同数之间进行消解，最后剩下的数即为出现次数最多那个数

缺点：需要判断是否真的次数超过一半，因为上述条件是必要条件但不是充分条件,时间效率没有hash表法好

O(n),O(1)

例：

1 2 2 2 3

i=0,t=0,res =1,t=1

i=1,不等，t-1=0

i=2,res =a\[2\] =2,t=1

i=3,相等，t+1=2

i=4,不等，t-1=1

\*/

class Solution

**\{**

public **:**

int MoreThanHalfNum\_Solution **(** vector **<** int **>** numbers **)**

**\{**

int result **=** numbers **\[** 0 **\];**

int times **=** 1 **;**

**for** **(** int i **=** 1 **;** i **<** numbers **.** size **();** i **++)**

**\{**

**if** **(** times **==** 0 **) **//候选数，

**\{**

result **=** numbers **\[** i **\];**

times **=** 1 **;**

**\}**

**else** **if** **(** numbers **\[** i **\]** **==** result **)** times **++;** //相等时次数加一，

**else** times **--;** //不等时减一

**\}**

times **=** 0 **;**

**for** **(** int ai **:** numbers **)** //判断是否真的次数超过一半

**\{**

**if** **(** ai **==** result **)** times **++;**

**\}**

**if** **(** times **>** numbers **.** size **()/** 2 **)** **return** result **;**

**else**   **return** 0 **;** //不存在

**\}**

**\};**

转载于:https://www.cnblogs.com/wikiwen/p/10224314.html

[LeetCode _ _offer _...]: https://blog.csdn.net/kk55guang2/article/details/85223256

发表评论取消回复

表情：

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

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

相关阅读

相关剑指offer：数组中出现次数超过一半的数字

题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次

桃扇骨/ 2022年08月05日 08:58/ 0 赞/ 170 阅读

相关《剑指offer》刷题笔记（时间效率）：数组中出现次数超过一半的数字

《剑指offer》刷题笔记（时间效率）：数组中出现次数超过一半的数字 -------------------- 转载请注明作者和出处：[http://blog.c

浅浅的花香味﹌/ 2022年06月05日 07:22/ 0 赞/ 53 阅读

相关剑指offer——数组中出现次数超过一半的数字

题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，超过

忘是亡心i/ 2022年05月31日 11:09/ 0 赞/ 177 阅读

相关剑指offer-题29：数组中出现次数超过一半的数字

题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次

深碍√TFBOYSˉ_/ 2022年05月28日 06:51/ 0 赞/ 111 阅读

相关剑指Offer | 数组中出现次数超过一半的数字

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

阳光穿透心脏的1/2处/ 2022年05月23日 03:15/ 0 赞/ 174 阅读

相关剑指offer: 数组中出现次数超过一半的数字

题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次

本是古典何须时尚/ 2022年04月10日 08:56/ 0 赞/ 193 阅读

相关【剑指offer】数组中出现次数超过一半的数字

数组中出现次数超过一半的数字题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,

￡神魔★判官ぃ/ 2022年03月30日 04:07/ 0 赞/ 179 阅读

相关剑指Offer-数组中出现次数超过一半的数字

题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次

一时失言乱红尘/ 2022年02月22日 04:45/ 0 赞/ 199 阅读

相关【LeetCode & 剑指offer刷题】数组题7：39 数组中出现次数超过一半的数字

[【LeetCode & 剑指offer 刷题笔记】目录（持续更新中...）][LeetCode _ _offer _...] 39 数组中出现次数超过一半的数字题目描

谁践踏了优雅/ 2021年10月01日 07:00/ 0 赞/ 158 阅读

相关剑指offer：数组中出现次数超过一半的数字

试题：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，超

待我称王封你为后i/ 2021年06月24日 16:09/ 0 赞/ 390 阅读