从品牌网站建设到网络营销策划,从策略到执行的一站式服务
让人瑟瑟发抖的面试题
。
。
。
来我们看一下题目
在一个 长度为n的数组里的所有数字都在0~n-的范围内。数组中某些数字是重复的,但不知道有几个数字重复伦理,也不知道每个数字重复了多少次,找出任意一个重复的数字
注意:时间复杂度O(n),空间复杂度O(1)
怎么解决勒???
分析:利用题目中0~n-1范围,可以运用数组下标和数组内容进行比较
if (arr[i] != arr[arr[i]]),如果不相等时,进行调换,相等时,直接返回值
来看看代码
#include
#define SIZE(arr) sizeof(arr)/sizeof(arr[0])//数组长度
void Swap(int *left, int *right)
{
int tmp = *left;
*left = *right;
*right = tmp;
}
int duplicate(int arr[],int len)
{
int i;
if (len < 0)
{
return 0;
}
for (i = 0; i < len; i++)
{
if (arr[i] < 0 || arr[i]>len - 1)//限定数字大小
{
return 0;
}
while (arr[i] != i)
{
if (arr[i] != i)
{
if (arr[i] != arr[arr[i]])//数组中数字是否等于以数字为下标的数字
{
Swap(&arr[i], &arr[arr[i]]);
}
else
{
return arr[i];
}
}
}
}
return 0;
}
int main()
{
int arr[] = {2,3,1,0,2,5,3};
printf("%d", duplicate(arr, SIZE(arr)));
return 0;
}
总结:数组中数据给定范围之后,可以多利用下标 i 进行求解
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
成都网站建设公司地址:成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220
成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.
专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网! | 成都网站建设哪家好? | 网站建设地图