搜索元素的有效方法
最近，我接受了一次采访，他们问我一个“ 搜索 ”问题。 问题是：
假设有一个（正）整数数组，每个元素都是+1或-1与其相邻元素比较。
例：
array = [4,5,6,5,4,3,2,3,4,5,6,7,8]; 现在搜索7并返回其位置。
我给了这个答案：
将值存储在临时数组中，对其进行排序，然后应用二进制搜索。
如果找到该元素，则返回其在临时数组中的位置。 （如果数字出现两次，则返回其第一次出现）
但是，他们似乎对此答案并不满意。
正确的答案是什么？ 问题来源于stack overflow
写回答
-
您可以使用通常大于1的步长进行线性搜索。关键的观察结果是，如果eg array[i] == 4和7尚未出现，则7的下一个候选项位于index处i+3。使用while循环可重复直接进入下一个可行的候选对象。
这是一个实现，略有概括。它找到k数组中的第一个匹配项（受+ = 1限制），或者-1如果没有出现则查找：
#include <stdio.h> #include <stdlib.h>
int first_occurence(int k, int array[], int n);
int main(void){ int a[] = {4,3,2,3,2,3,4,5,4,5,6,7,8,7,8}; printf("7 first occurs at index %d\n",first_occurence(7,a,15)); printf("but 9 first "occurs" at index %d\n",first_occurence(9,a,15)); return 0; }
int first_occurence(int k, int array[], int n){ int i = 0; while(i < n){ if(array[i] == k) return i; i += abs(k-array[i]); } return -1; } 输出：
7 first occurs at index 11 but 9 first "occurs" at index -1
2020-02-08 13:48:36赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
