原文地址: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,请找到t在A中的位置。除了依次遍历,还有更好的方法么?
这道题目的解法非常有趣。
数组第一个数为array[0], 要找的数为y,设t = abs(y - array[0])。由于每个相邻的数字之差的绝对值为1。故第t个位置之前的数肯定都比y小(个人认为还有可能比之前的数都比y大的可能)。因此直接定位到array[t],重新计算t,t = abs(y – array[t]),再重复上述步骤即可。这种算法主要利用了当前位置的数与查找数的差来实现跨越式搜索。算法效率要比遍历数组的算法要高一些,并且易于实现。完整的代码如下:
- // 【白话经典算法系列之十五】“一步千里”之数组找数
- // by MoreWindows( http://blog.csdn.net/MoreWindows )
- // 欢迎关注http://weibo.com/morewindows
- #include <stdio.h>
- #include <math.h>
- void PrintfArray(int a[], int n)
- {
- for (int i = 0; i < n; i++)
- printf("%d ", a[i]);
- putchar('\n');
- }
- int FindNumberInArray(int arr[], int n , int find_number)
- {
- int next_arrive_index = abs(find_number - arr[0]);
- while (next_arrive_index < n)
- {
- if (arr[next_arrive_index] == find_number)
- return next_arrive_index;
- next_arrive_index += abs(find_number - arr[next_arrive_index]);
- }
- return -1;
- }
- int main()
- {
- printf(" 【白话经典算法系列之十五】“一步千里”之数组找数\n");
- printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n");
- printf(" -- http://blog.csdn.net/morewindows/article/details/10645269 -- \n\n");
- const int MAXN = 10;
- int arr[MAXN] = {4,5,6,5,6,7,8,9,10,9};
- PrintfArray(arr, MAXN);
- for (int i = 0; i < MAXN; i++)
- printf("查找%d \t下标为%d\n", arr[i], FindNumberInArray(arr, MAXN, arr[i]));
- printf("查找%d \t下标为%d\n", -1, FindNumberInArray(arr, MAXN, -1));
- printf("查找%d \t下标为%d\n", 0, FindNumberInArray(arr, MAXN, 0));
- printf("查找%d \t下标为%d\n", 100, FindNumberInArray(arr, MAXN, 100));
- return 0;
- }
相关推荐
八年级政治上册 第九课《一步之遥》千里之堤 溃于蚁穴 课件 教科版.ppt
【《.千里之马》阅读答案翻译译文中考语文试题】 千里之马 译文.docx
四川省青神县初级中学校八年级政治上册 第九课 一步之遥—千里之堤,溃于蚁穴2导学案(无答案) 教科版
此资源诗华为mate60的预设主题“诗野千里”的hwt文件
第课千里之堤,溃于蚁穴.ppt
千里走壶口
第18课千里之堤,溃于蚁穴.ppt
欲穷千里目,更上一层楼
通达信牛行千里主图指标.doc
千里目远程监控系统免杀版无脱千里目远程监控系统免杀版无脱千里目远程监控系统免杀版无脱
题目描述:给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 num1 成为一个有序数组。 说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 你可以...
八年级政治上册千里之堤溃于蚁穴课件教科版.ppt
千里之堤毁于蚁穴,百年安全成于细节.docx
千里之堤毁于蚁穴,百年安全成于细节.doc
给定一个整数数组nums和一个目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。 链表 栈 哈希表 双指针 队列 堆 字符串 树 图 数学 递归 分治 动态规划 贪心算法 回溯 广度优先...
不积跬步,无以至千里;不积小流,无以成江海。愿与诸君共勉! 【题目】27.移除元素 题目描述:给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于val 的元素,并返回移除后数组的新长度。...
积跬步方能至千里,2020看安科生物厚积薄发.pdf
易语言千里模块 更改 易语言内置浏览器IE版本等等 一条命令搞定
失之毫厘,差之千里作文.doc