题目:数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字。
分析:这是一道广为流传的面试题,包括百度、微软和Google在内的多家公司都曾经采用过这个题目。要几十分钟的时间里很好地解答这道题,除了较好的编程能力之外,还需要较快的反应和较强的逻辑思维能力。
看到这道题,我们马上就会想到,要是这个数组是排序的数组就好了。如果是排序的数组,那么我们只要遍历一次就可以统计出每个数字出现的次数,这样也就能找出符合要求的数字了。题目给出的数组没有说是排好序的,因此我们需要给它排序。排序的时间复杂度是O(nlogn),再加上遍历的时间复杂度O(n),因此总的复杂度是O(nlogn)。
接下来我们试着看看能不能想出更快的算法。前面思路的时间主要是花在排序上。我们可以创建一个哈希表来消除排序的时间。哈希表的键值(Key)为数组中的数字,值(Value)为该数字对应的次数。有了这个辅助的哈希表之后,我们只需要遍历数组中的每个数字,找到它在哈希表中对应的位置并增加它出现的次数。这种哈希表的方法在数组的所有数字都在一个比较窄的范围内的时候很有效。本博客系列的第13题就是一个应用哈希表的例子。不过本题并没有限制数组里数字的范围,我们要么需要创建一个很大的哈希表,要么需要设计一个很复杂的方法来计算哈希值。因此总体说来这个方法还不是很好。
前面两种思路都没有考虑到题目中数组的特性:数组中有个数字出现的次数超过了数组长度的一半。也就是说,有个数字出现的次数比其他所有数字出现次数的和还要多。因此我们可以考虑在遍历数组的时候保存两个值:一个是数组中的一个数字,一个是次数。当我们遍历到下一个数字的时候,如果下一个数字和我们之前保存的数字相同,则次数加1。如果下一个数字和我们之前保存的数字不同,则次数减1。如果次数为零,我们需要保存下一个数字,并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多,那么要找的数字肯定是最后一次把次数设为1时对应的数字。
基于这个思路,我们不难写出如下代码:
bool g_bInputInvalid =
false;
//////////////////////////////////////////////////////////////////////////
// Input: an array with "length" numbers.A number in the array
// appear more than "length / 2 + 1" times.
// Output: If the input is valid, return the number appearing more than
// "length / 2 + 1" times. Otherwise, return 0 and set flag g_bInputInvalid
// to be true.
//////////////////////////////////////////////////////////////////////////
int MoreThanHalfNum(int* numbers,unsigned
int length)
{
if(numbers == NULL && length == 0)
{
g_bInputInvalid = true;
return 0;
}
g_bInputInvalid = false;
int result = numbers[0];
int times = 1;
for(int i = 1; i < length; ++i)
{
if(times == 0)
{
result = numbers[i];
times = 1;
}
else if(numbers[i] == result)
times++;
else
times--;
}
// verify whether the input is valid
times = 0;
for(int i = 0; i < length; ++i)
{
if(numbers[i] == result)
times++;
}
if(times * 2 <= length)
{
g_bInputInvalid = true;
result = 0;
}
return result;
}
在上述代码中,有两点值得讨论:
我们需要考虑当输入的数组或者长度无效时,如何告诉函数的调用者输入无效。关于处理无效输入的几种常用方法,在本博客系列的第17题中有详细的讨论;
本算法的前提是输入的数组中的确包含一个出现次数超过数组长度一半的数字。如果数组中并不包含这么一个数字,那么输入也是无效的。因此在函数结束前我还加了一段代码来验证输入是不是有效的。
分享到:
相关推荐
数组中出现次数超过一半的数字.md
数组中出现次数超过一半的数字数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。示例 1:输入: [1, 2, 3, 2, 2, 2, 5, 4, 2
java基础面试题数组中出现次数超过一半的数字本资源系百度网盘分享地址
在本篇文章中我们给大家分享了php如何实现数组中出现次数超过一半的数字的统计方法,有需要的朋友们参考下。
题目位置题解* 思路一:* 1、使用 map 存储每一个数字出现的次数,然后找到最大的* 思路二:* 1、数组中有一个数字出现的次数超过数组长度的一半 说明在这
【出现次数超过一半的数,它的出现次数比其他所有数字出现次数的总和还要多】这个操作的思想:(自己猜的)相当于将所有数分成两半 用最多的和其余每个抵消完 还有的话
# 返回most_common(k)的是最常出现的k个元素的(元素,次数)tuple组成的数组# 先从数组中取出最长出现(元素,次数)tuple,再分别从tup
如果前面查找了 i 个元素,且 cnt == 0,说明前 i 个元素没有 majority,或者有 majority,但是出现的次数少于 i / 2 ,因为如果
1. 题目描述 2. 思路分析 3. 代码
题目:数组中出现次数超过一半的数字 题:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此...
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
比较容易想到的思路是直接对数组排序,那中间那个值就是我们想要的值,但这样的想法明显排序后会对输入的数组顺序有影响,所以我们可能需要换一种思路。数组中有一个数字出
主要介绍了PHP实现找出数组中出现次数超过数组长度一半的数字算法,涉及php数组的遍历、统计、判断等相关操作技巧,需要的朋友可以参考下
主要介绍了基于Java代码实现数字在数组中出现次数超过一半的相关资料,需要的朋友可以参考下
主要介绍了Python 找出出现次数超过数组长度一半的元素实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
数组中出现次数超过一半的数字.py 最小的k个数.py 连续子数组的最大和.py n整数中1出现的次数.py 数字序列中的某一位数字.py 把数组拍成最小的数字.py 把数字翻译成字符串.py 礼物的最大价值.py 最长不含重复字符的...
39.数组中出现次数超过一半的数字 Array 常考 40.最小的k个数 Heap 41.数据流中的中位数 常考 42.连续子数组最大和 Dynamic Programming 43.整数中1出现的次数 Bit Manipulation 关注 44.数字序列中某一位的数字 ...
数组中出现次数超过一半的数字30.连续子数组最大和32.把数组排出最小的数35.数组中的逆序对37.数字在排序数组中出现的次数40.数组中自出现过一次的数字50.数组中的重复数字51.构建乘积数组 数组篇 1.二维数组中的...
Java面试 Java超级经典100问题 Java高级开发工程师必备 Java面试宝典 ...数组中出现次数超过一半的数字.30.找出最小的K个数31.连续子数组的最大和.32.从1到整数n中1出现的次数.33.把数组中的数排成一个最小的数.3