`

“一步千里”之数组找数

 
阅读更多

原文地址:http://blog.csdn.net/morewindows/article/details/10645269

首先看看题目要求(题目来源:http://weibo.com/lirenchen,特此鸣谢):

有这样一个数组A,大小为n,相邻元素差的绝对值都是1。如:A={4,5,6,5,6,7,8,9,10,9}现在,给定A和目标整数t,请找到tA中的位置。除了依次遍历,还有更好的方法么?

这道题目的解法非常有趣。

数组第一个数为array[0], 要找的数为y,设t = abs(y - array[0])。由于每个相邻的数字之差的绝对值为1。故第t个位置之前的数肯定都比y小(个人认为还有可能比之前的数都比y大的可能)。因此直接定位到array[t],重新计算tt = abs(y – array[t]),再重复上述步骤即可。这种算法主要利用了当前位置的数与查找数的差来实现跨越式搜索。算法效率要比遍历数组的算法要高一些,并且易于实现。完整的代码如下:

  1. // 【白话经典算法系列之十五】“一步千里”之数组找数  
  2. //  by MoreWindows( http://blog.csdn.net/MoreWindows )   
  3. //  欢迎关注http://weibo.com/morewindows  
  4. #include <stdio.h>  
  5. #include <math.h>  
  6. void PrintfArray(int a[], int n)    
  7. {    
  8.   for (int i = 0; i < n; i++)    
  9.       printf("%d ", a[i]);    
  10.   putchar('\n');    
  11. }   
  12. int FindNumberInArray(int arr[], int n , int find_number)  
  13. {  
  14.   int next_arrive_index = abs(find_number - arr[0]);  
  15.   while (next_arrive_index < n)  
  16.   {  
  17.     if (arr[next_arrive_index] == find_number)  
  18.       return next_arrive_index;  
  19.     next_arrive_index += abs(find_number - arr[next_arrive_index]);  
  20.   }  
  21.   return -1;  
  22. }  
  23. int main()  
  24. {  
  25.   printf("    【白话经典算法系列之十五】“一步千里”之数组找数\n");  
  26.   printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n");  
  27.   printf(" -- http://blog.csdn.net/morewindows/article/details/10645269 -- \n\n");  
  28.   
  29.   const int MAXN = 10;  
  30.   int arr[MAXN] = {4,5,6,5,6,7,8,9,10,9};  
  31.   PrintfArray(arr, MAXN);  
  32.   for (int i = 0; i < MAXN; i++)  
  33.     printf("查找%d   \t下标为%d\n", arr[i], FindNumberInArray(arr, MAXN, arr[i]));  
  34.   
  35.   printf("查找%d   \t下标为%d\n", -1, FindNumberInArray(arr, MAXN, -1));  
  36.   printf("查找%d   \t下标为%d\n", 0, FindNumberInArray(arr, MAXN, 0));  
  37.   printf("查找%d   \t下标为%d\n", 100, FindNumberInArray(arr, MAXN, 100));  
  38.   return 0;  

分享到:
评论

相关推荐

    八年级政治上册 第九课《一步之遥》千里之堤 溃于蚁穴 课件 教科版.ppt

    《一步之遥——千里之堤,溃于蚁穴》这节课是八年级政治上册的内容,主要探讨了青少年时期的一些行为问题以及它们可能引发的严重后果。课程关注的重点在于不良行为与严重不良行为之间的紧密联系,以及这些行为如何...

    【《.千里之马》阅读答案翻译译文中考语文试题】 千里之马 译文.docx

    【《.千里之马》阅读答案翻译译文中考语文试题】 千里之马 译文.docx

    四川省青神县初级中学校八年级政治上册 第九课 一步之遥—千里之堤,溃于蚁穴2导学案(无答案) 教科版

    四川省青神县初级中学校八年级政治上册 第九课 一步之遥—千里之堤,溃于蚁穴2导学案(无答案) 教科版

    华为Mate60主题诗野千里

    此资源诗华为mate60的预设主题“诗野千里”的hwt文件

    易语言千里模块更改语言内置浏览器IE版本

    "千里模块"是易语言中的一个特色组件,它提供了一系列实用的功能,方便开发者进行软件开发。在本案例中,我们将探讨如何使用易语言千里模块来更改其内置浏览器的IE版本。 内置浏览器通常用于在应用程序中展示网页...

    千里目远程监控系统免杀 2.1.rar

    【标题】:“千里目远程监控系统免杀 2.1.rar”揭示了这是一款名为“千里目”的远程监控系统的无病毒版本,版本号为2.1,并且它被压缩成RAR格式的文件。 【描述】:“千里目远程监控系统免杀版无脱千里目远程监控...

    千里之外-周杰伦〖简易动听〗钢琴曲谱双手数字简谱.pdf

    《千里之外》作为他的代表作之一,体现了他对中国传统音乐元素的巧妙运用,以及对现代流行曲调的创新结合。 4. **简易动听**:这个标签意味着曲谱设计注重易学性和音乐性,旨在使初学者能够快速上手,同时保持曲目...

    第课千里之堤,溃于蚁穴.ppt

    标题中的“千里之堤,溃于蚁穴”源自中国古代的成语,意指小小的疏忽可能导致巨大的损失,这里的主题被应用于青少年的行为教育,强调了不良行为和违法犯罪之间的紧密联系。描述中提到的内容着重于分析青少年如何从...

    LeeCode每日一题–合并两个有序数组

       题目描述:给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 num1 成为一个有序数组。    说明:      初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。      你可以...

    千里之堤毁于蚁穴,百年安全成于细节.doc

    千里之堤毁于蚁穴,百年安全成于细节.doc

    leetcode卡-LeetCode_cpp:不积跬步无以至千里,不积小流无以成江河。坚持每天打卡!

    给定一个整数数组nums和一个目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。   链表 栈 哈希表 双指针 队列 堆 字符串 树 图 数学 递归 分治 动态规划 贪心算法 回溯 广度优先...

    LeeCode每日一题–移除元素

       不积跬步,无以至千里;不积小流,无以成江海。愿与诸君共勉!   【题目】27.移除元素    题目描述:给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于val 的元素,并返回移除后数组的新长度。...

    通达信牛行千里主图指标.doc

    "通达信牛行千里主图指标"是一个用于股票交易分析的自定义技术指标,它在通达信这个证券分析软件上使用。该指标的设计目的是帮助投资者识别股票的买入和卖出时机,尤其强调在市场波动中寻找持续上涨的潜力股,即所谓...

    积跬步方能至千里,2020看安科生物厚积薄发.pdf

    积跬步方能至千里,2020看安科生物厚积薄发.pdf

    第18课千里之堤,溃于蚁穴.ppt

    本课主题为“千里之堤,溃于蚁穴”,强调的是从小错误到大问题的演变过程,尤其在青少年教育和法制意识培养方面具有重要意义。以下是从课件内容中提炼出的相关知识点: 1. **小错与大错的联系**:小错误和大错误...

    欲穷千里目,更上一层楼

    课程《欲穷千里目,更上一层楼》主要关注高中生的生涯规划教育,旨在通过一系列教学活动和方法,培养学生的生涯规划意识和能力。以下内容详细解读了该课程的教学策略和实施要点。 在实施生涯规划教育的起步探索阶段...

    千里扫鸡软件

    【标题】:“千里扫鸡软件” “千里扫鸡软件”是一个独特的术语,它可能是某种特定的计算机程序或者工具的名称,但在这个上下文中,并没有提供足够的信息来详细解释这个软件的功能或用途。通常,这样的软件可能涉及...

    KDE综览,千里孤坟MM出品

    "千里孤坟MM"的这份使用说明深入浅出地介绍了KDE的各种特性和使用技巧,帮助用户更好地理解和利用这个强大的桌面系统。 **一、KDE的核心特点** 1. **自定义性**:KDE允许用户根据个人喜好调整界面的各个方面,包括...

    千里之堤毁于蚁穴,百年安全成于细节.docx

    #### 一、引言:千里之堤,溃于蚁穴——安全意识的重要性 - **出处与含义**:“千里之堤,溃于蚁穴”源自中国古代哲学家韩非子的作品《韩非子·喻老》,这句话强调了即使是微小的安全隐患也可能导致巨大的损失。 - ...

Global site tag (gtag.js) - Google Analytics