《剑指Offer》面试题：超过数组长度的一半的数

2024-05-14 05:08
文章标签 数组 面试题 offer 长度 超过 一半

本文主要是介绍《剑指Offer》面试题：超过数组长度的一半的数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

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

思路
解决此题的思路有很多。
1、最容易想到的方法：将数组进行排序，取中位数即可。但是时间复杂度为O(nlogn)

2、考虑用哈希，key保存数组元素，value保存出现的次数，这样在遍历O(n)能做出key-value的映射，再用O(k)(k为需要的槽的个数)可以找出出现次数超过一半的key，但是由于数组中元素的大小范围未知，因此使用这种方法，首先不能确定哈希表的大小，即使通过遍历一次求得了最大值，范围很大的话，又要花费很大心思设计很好的哈希函数来完成key-value的映射，且不具有通用性，而且还要考虑数组中元素为负值的情况，因此用哈希表不合适。如果说数字只有0-9的话可以考虑设计一个Hash table，遍历一次就能知道每个数字出现的次数。

3、思路1中需要将数组进行排序，而事实上可以不用对数组进行排序，
或者说仅部分排序，受快速排序的partition函数的启发，
我们可以利用反复调用partition函数来求的该数字。我们现在数组中随机选取一个数字，
而后通过Partition函数返回该数字在数组中的索引index，如果index刚好等于n/2，则这个数字便是数组的中位数，也即是要求的数，
如果index大于n/2，则中位数肯定在index的左边，在左边继续寻找即可，反之在右边寻找。这样可以只在index的一边寻找，
而不用两边都排序，减少了一半排序时间。这种情况的平均时间复杂度大致为：T(n) = n+n/2+n/4+n/8+….+1，很明显当n很大时，T(n)趋近于2n，
也就是说平均情况下时间复杂度为O(n),但是这种情况下，最坏的时间复杂度依然为O(n*n)，最坏情况下，index总是位于数组的最左或最右边，
这样时间复杂度为T(n) = n+n-1+n-2+n-3+….+1 = n(n-1)/2，显然，时间复杂度为O(n*n)，空间复杂度为O(1)。

思路3的实现代码如下


/*
题目描述：
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。输入：
每个测试案例包括2行：第一行输入一个整数n（1<=n<=100000），表示数组中元素的个数。第二行输入n个整数，表示数组中的每个元素，这n个整数的范围是[1,1000000000]。输出：
对应每个测试案例，输出出现的次数超过数组长度的一半的数，如果没有输出-1。样例输入：
9
1 2 3 2 2 2 5 4 2
样例输出：
2
*/ #include<stdio.h>
#include<stdlib.h>//定义一个全局变量，用来指示输入的数据中是否有效。这里的“有效”指的是：输入的数据中次数超过一半的数
bool isValid=false; 
/*
函数功能：判断在数组arr中result出现的次数是否为arr长度的一半以上。 
参数的说明
@param arr：数组的指针
@param len:数组的长度
@param result：待检测的数 
*/
bool isMoreThanHalfInArray(int *arr,int n,int result){if(arr==NULL||n<=0){return false;}int times=0;for(int i=0;i<n;i++){if(arr[i]==result){times++;}}bool isHalf=false;if(times*2>=n){isHalf=true;}return isHalf;}
void swap(int *a,int *b){if(a!=NULL&&b!=NULL){int temp=*a;*a=*b;*b=temp;}
}
int partition(int *arr,int begin,int end){if(arr==NULL||begin<0||end<0||begin>end){return -1;}int index=begin;//选取首元素为主元for(int i=begin;i<=end;i++) {if(arr[i]<arr[begin]){index++;swap(&arr[index],&arr[i]);}}swap(&arr[begin],&arr[index]);//将主元交换到他应该在的位置return index; }int findMoreThanHalfNumInArray(int *arr,int n){if(arr==NULL||n<=0){//输入数据无效isValid=false; return -1;}int begin=0;int end=n-1;int mid=n>>1;int index=partition(arr,begin,end);//利用快排得到主元的索引while(index!=mid) {if(index>mid){//说明mid在index的左边end=index-1;index=partition(arr,begin,end); }else{begin=index+1;index=partition(arr,begin,end);}}//上面的while循环就找到的中位数，但是在返回之前，还是需要判断此种位数的出现的次数是否达到了数组长度的一半以上。若达到了，则返回就可以了bool isMoreThanHalf=isMoreThanHalfInArray(arr,n,arr[index]);if(!isMoreThanHalf){isValid=false;return -1;} return arr[index]; }
int main(void){int n;while(scanf("%d",&n)!=EOF&&n>0){int *arr=(int *)malloc(n*sizeof(int));if(arr==NULL)exit(EXIT_FAILURE);for(int i=0;i<n;i++){int val;scanf("%d",&val);arr[i]=val;}isValid=true;int result=findMoreThanHalfNumInArray(arr,n);if(isValid){printf("%d",result);}else{printf("-1");}printf("\n");}return 0;
}

4、出现的次数超过数组长度的一半，表明这个数字出现的次数比其他数字出现的次数的总和还多。所以我们可以考虑每次删除两个不同的数，那么在剩下的数中，出现的次数仍然超过总数的一半。
通过不断重复这个过程，不断排除掉其它的数，最终找到那个出现次数超过一半的数字。
这个方法，免去了上述思路一的排序，也避免了思路2中空间O（N）的开销，总得说来，时间复杂度只有O（N），空间复杂度为O（1），不失为最佳方法。
例：数组 a[5]={0,1,2,1,1};
我们要查找的数字为1，操作步骤为：遍历整个数组，然后每次删除不同的两个数字，过程如下：
0 1 2 1 1 =>2 1 1=>1

具体实现：我们在考虑删除两个不同的数字的时候，实际上可以通过计数来实现，而不是物理上真正的删除。
在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，
如果下一个数字和我们之前保存的数字相同，则次数加1。如果下一个数字和我们之前保存的数字不同，则次数减1。
如果次数为零，我们需要保存下一个数字，并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，因此，最后一次把次数设定为1的数可能是我们要寻找的数，但不是一定。

注意：那么要找的数字肯定是最后一次把次数设为1时对应的数字，网上都是这么说，但此句话欠妥，例如：数组为1、3、2；则最后一次把次数设为1的数字为2，但数组中并没有次数多于一般的数。因此，最后还需要判断。

下面的实现代码是按照思路4来实现的。

/*
测试函数的要求如下输入：
每个测试案例包括2行：第一行输入一个整数n（1<=n<=100000），表示数组中元素的个数。第二行输入n个整数，表示数组中的每个元素，这n个整数的范围是[1,1000000000]。输出：
对应每个测试案例，输出出现的次数超过数组长度的一半的数，如果没有输出-1。样例输入：
9
1 2 3 2 2 2 5 4 2
样例输出：
2
*/ #include<stdio.h>
#include<stdlib.h>bool isExist; //定义一个全局变量，用来标识数组中是否存在超过一半的数。 当为false时，表示，不存在并输出-1.也是为了区分isExist=true，而超过一半的数为-1的情况。 
/*
函数功能：判断在数组arr中result出现的次数是否为arr长度的一半以上。 
参数的说明
@param arr：数组的指针
@param len:数组的长度
@param result：待检测的数 
*/
bool isMoreThanHalfNumInArray(int *arr,int len,int result){if(arr==NULL||len<=0){isExist=false;return false;}int times=0;for(int i=0;i<len;i++){if(arr[i]==result){times++;}}bool isMoreThanHalf=false; if(times*2>=len){isMoreThanHalf=true;}return isMoreThanHalf;}
/*
函数的功能：在数组中寻找次数超过一半的数。 
*/ 
int findMoreThanHalfNumInArray(int  *arr,int len){if(arr==NULL||len<=0){isExist=false;return -1;}int result;//用来保存结果 int times=0;//用来保存次数 for(int i=0;i<len;i++){if(times==0){//如果times为零时，则应该保存当前的数，并将times=1result=arr[i];times=1; }else if(result==arr[i]){times++;}else{times--;}}//到这里为止，我们还需要判断reuslt是否真的是数组中次数出现一半的数字。if(!isMoreThanHalfNumInArray(arr,len,result)) {isExist=false;return -1;}return result;} 
int main(void){int n;while(scanf("%d",&n)!=EOF){if(n>0){int *arr=(int *)malloc(n*sizeof(int));if(arr==NULL){exit(EXIT_FAILURE);}int val;for(int i=0;i<n;i++){scanf("%d",&val);arr[i]=val;}//开始寻找超过一半的数在数组中isExist=true;int result=findMoreThanHalfNumInArray(arr,n);if(isExist){printf("%d",result);} else{printf("-1");}printf("\n");}}return 0;
}

这篇关于《剑指Offer》面试题：超过数组长度的一半的数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/987830。

相关文章

hdu2241（二分+合并数组）

hdu2241（二分+合并数组）

题意：判断是否存在a+b+c = x，a，b，c分别属于集合A,B,C 如果用暴力会超时，所以这里用到了数组合并，将b,c数组合并成d，d数组存的是b，c数组元素的和，然后对d数组进行二分就可以了 代码如下（附注释）： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...
荣耀嵌入式面试题及参考答案

荣耀嵌入式面试题及参考答案

在项目中是否有使用过实时操作系统？ 在我参与的项目中，有使用过实时操作系统。实时操作系统（RTOS）在对时间要求严格的应用场景中具有重要作用。我曾参与的一个工业自动化控制项目就采用了实时操作系统。在这个项目中，需要对多个传感器的数据进行实时采集和处理，并根据采集到的数据及时控制执行机构的动作。实时操作系统能够提供确定性的响应时间，确保关键任务在规定的时间内完成。 使用实时操作系统的
阅读更多...
一些其他面试题

一些其他面试题

阿里二面：那你来说说定时任务？单机、分布式、调度框架下的定时任务实现是怎么完成的？懵了。。_哔哩哔哩_bilibili 1.定时算法 累加，第二层每一个格子是第一层的总时间400 ms= 20 * 20ms 2.MQ消息丢失 阿里二面：高并发场景下引进消息队列有什么问题？如何保证消息只被消费一次？真是捏了一把汗。。_哔哩哔哩_bilibili 发送消息失败
阅读更多...
C语言：柔性数组

C语言：柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t；t = malloc(sizeof(Test) + 11);strcpy(t->arr,
阅读更多...
C 语言基础之数组

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组，顾名思义，就是一组数。 假如班上有 30 个同学，让你编程统计每个人的分数，求最高分、最低分、平均分等。如果不知道数组，你只能这样写代码： int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou
阅读更多...
zookeeper相关面试题

zookeeper相关面试题

zk的数据同步原理？zk的集群会出现脑裂的问题吗？zk的watch机制实现原理？zk是如何保证一致性的？zk的快速选举leader原理？zk的典型应用场景zk中一个客户端修改了数据之后，其他客户端能够马上获取到最新的数据吗？zk对事物的支持？ 1. zk的数据同步原理？ zk的数据同步过程中，通过以下三个参数来选择对应的数据同步方式 peerLastZxid：Learner服务器（Follo
阅读更多...
java常用面试题-基础知识分享

java常用面试题-基础知识分享

什么是Java？ Java是一种高级编程语言，旨在提供跨平台的解决方案。它是一种面向对象的语言，具有简单、结构化、可移植、可靠、安全等特点。 Java的主要特点是什么？ Java的主要特点包括： 简单性：Java的语法相对简单，易于学习和使用。面向对象：Java是一种完全面向对象的语言，支持封装、继承和多态。跨平台性：Java的程序可以在不同的操作系统上运行，称为"Write once,
阅读更多...
计算数组的斜率，偏移，R2

计算数组的斜率，偏移，R2

模拟Excel中的R2的计算。         public bool fnCheckRear_R2(List<double[]> lRear, int iMinRear, int iMaxRear, ref double dR2)         {             bool bResult = true;             int n = 0;             dou
阅读更多...
C# double[] 和Matlab数组MWArray[]转换

C# double[] 和Matlab数组MWArray[]转换

C# double[] 转换成MWArray[], 直接赋值就行             MWNumericArray[] ma = new MWNumericArray[4];             double[] dT = new double[] { 0 };             double[] dT1 = new double[] { 0,2 };
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2