#include<stdio.h>
#include<stdlib.h>
void swap(int* data1,int* data2)
{
int temp=*data1;
*data1=*data2;
*data2=temp;
}
int partition(int data[],int length,int start,int end)//基于Partition函数的O(n)算法
{
if(data==NULL||length<=0||start<0||end>=length)
return 0;
int index=0;
swap(&data[index],&data[end]);
int small=start-1;
for(index=start;index<end;++index)
{
if(data[index]<data[end])
{
++small;
if(small!=index)
swap(&data[index],&data[small]);
}
}
++small;
swap(&data[small],&data[end]);
return small;
}
bool bInputInvalid=false;
bool checkInvalidArray(int* numbers,int length)
{
bInputInvalid=false;
if(numbers==NULL&&length<=0)
bInputInvalid=true;
return bInputInvalid;
}
bool checkMoreThanHalf(int* numbers,int length,int number)
{
int times=0;
for(int i=0;i<length;i++)
{
if(numbers[i]==number)
times++;
}
bool isMoreThanHalf=true;
if(times*2<=length)
{
bInputInvalid=true;
isMoreThanHalf=false;
}
return isMoreThanHalf;
}
/*
int moreThanHalfNum(int* numbers,int length)
{
if(checkInvalidArray(numbers,length))
return 0;
int middle=length>>1;
int start=0;
int end=length-1;
int index=partition(numbers,length,start,end);
while(index!=middle)
{
if(index>middle)
{
end=index-1;
index=partition(numbers,length,start,end);
}
else
{
start=index+1;
index=partition(numbers,length,start,end);
}
}
int result=numbers[middle];
if(!checkMoreThanHalf(numbers,length,result))
result=0;
return result;
}
*/
int moreThanHalfNum(int* numbers,int length)
{
if(checkInvalidArray(numbers,length))
return 0;
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--;
}
if(!checkMoreThanHalf(numbers,length,result))
return 0;
return result;
}
int main()
{
int length;
scanf("%d",&length);
int numbers[length];
for(int i=0;i<length;i++)
scanf("%d",&numbers[i]);
printf("%d",moreThanHalfNum(numbers,length));
return 0;
}
题目:
数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字
分析:
看到这道题,我们马上就会想到,要是这个数组是排序的数组就好了。如果是排序的数组,
那么我们只要遍历一次就可以统计出每个数字出现的次数,这样也就能找出符合要求的数字了。
题目给出的数组没有说是排好序的,因此我们需要给它排序。排序的时间复杂度是O(nlogn),
再加上遍历的时间复杂度O(n),因此总的复杂度是O(nlogn)。
接下来我们试着看看能不能想出更快的算法。前面思路的时间主要是花在排序上。
我们可以创建一个哈希表来消除排序的时间。哈希表的键值(Key)为数组中的数字,值(Value)为该数字对应的次数。
有了这个辅助的哈希表之后,我们只需要遍历数组中的每个数字,找到它在哈希表中对应的位置并增加它出现的次数。
这种哈希表的方法在数组的所有数字都在一个比较窄的范围内的时候很有效。
前面两种思路都没有考虑到题目中数组的特性:
数组中有个数字出现的次数超过了数组长度的一半。也就是说,有个数字出现的次数比其他所有数字出现次数的和还要多。
因此我们可以考虑在遍历数组的时候保存两个值:一个是数组中的一个数字,一个是次数。当我们遍历到下一个数字的时候,
如果下一个数字和我们之前保存的数字相同,则次数加1。如果下一个数字和我们之前保存的数字不同,则次数减1。
如果次数为零,我们需要保存下一个数字,并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多,
那么要找的数字肯定是最后一次把次数设为1时对应的数字。
结果:
分享到:
相关推荐
数组中出现次数超过一半的数字数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。示例 1:输入: [1, 2, 3, 2, 2, 2, 5, 4, 2
数组中出现次数超过一半的数字.md
java基础面试题数组中出现次数超过一半的数字本资源系百度网盘分享地址
题目位置题解* 思路一:* 1、使用 map 存储每一个数字出现的次数,然后找到最大的* 思路二:* 1、数组中有一个数字出现的次数超过数组长度的一半 说明在这
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。 两种方式: 1...
题:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。 解题思路...
主要介绍了PHP实现找出数组中出现次数超过数组长度一半的数字算法,涉及php数组的遍历、统计、判断等相关操作技巧,需要的朋友可以参考下
题目在一个长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中至少有一个数字是重复的。如果1~m的数字的数目等于m,则不能直接判断这一半区间是否包含重复
比较容易想到的思路是直接对数组排序,那中间那个值就是我们想要的值,但这样的想法明显排序后会对输入的数组顺序有影响,所以我们可能需要换一种思路。数组中有一个数字出
# 返回most_common(k)的是最常出现的k个元素的(元素,次数)tuple组成的数组# 先从数组中取出最长出现(元素,次数)tuple,再分别从tup
【出现次数超过一半的数,它的出现次数比其他所有数字出现次数的总和还要多】这个操作的思想:(自己猜的)相当于将所有数分成两半 用最多的和其余每个抵消完 还有的话
主要介绍了Python 找出出现次数超过数组长度一半的元素实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
1. 题目描述 2. 思路分析 3. 代码
如果前面查找了 i 个元素,且 cnt == 0,说明前 i 个元素没有 majority,或者有 majority,但是出现的次数少于 i / 2 ,因为如果
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
主要介绍了基于Java代码实现数字在数组中出现次数超过一半的相关资料,需要的朋友可以参考下
1.有序数组中有一半的元素小于等于数组的中位数,有一半的元素大于等于中位数(如果数组中元素个数是奇数,那么这里的一半并不是严格意义的1/2) 2.如果我们去掉其中一个数组比中位数小的k个数,再去掉另一个数组中...
数组中出现次数超过一半的数字.py 最小的k个数.py 连续子数组的最大和.py n整数中1出现的次数.py 数字序列中的某一位数字.py 把数组拍成最小的数字.py 把数字翻译成字符串.py 礼物的最大价值.py 最长不含重复字符的...
本文实例讲述了Python实现查找数组中任意第k大的数字算法。分享给大家供大家参考,具体如下: 模仿partion方法,当high=low小于k的时候,在后半部分搜索,当high=low大于k的时候,在前半部分搜索。与快排不同的是,...