搜索元素的有效方法
最近我参加了一个面试，他们问了我一个“搜索性”的问题。
问题是：
假设有一个(正)整数数组，其中每个元素与其相邻元素相比要么是
+1，要么是-1。
示例：
array = 4,5,6,5,4,3,2,3,4,5,6,7,8；
现在搜索7并返回其位置。
我给出了这个答案：
将这些值存储在一个临时数组中，对它们进行排序，然后应用二进制搜索。
如果找到该元素，则返回其在临时数组中的位置。
(如果该数字出现两次，则返回其第一次出现)
但是，他们似乎对这个答案并不满意。
正确的答案是什么？
回答 8
Stack Overflow用户
发布于 2015-12-27 23:02:21
你可以用通常大于1的步长进行线性搜索。关键的观察是，如果array[i] == 4和7还没有出现，那么7的下一个候选者是索引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 -1Stack Overflow用户
发布于 2015-12-27 23:08:29
你的方法太复杂了。您不需要检查每个数组元素。第一个值是4，所以7至少有7-4个元素，您可以跳过这些元素。
#include <stdio.h>
#include <stdlib.h>
int main (void)
{
int array[] = {4,5,6,5,4,3,2,3,4,5,6,7,8};
int len = sizeof array / sizeof array[0];
int i = 0;
int steps = 0;
while (i < len && array[i] != 7) {
i += abs(7 - array[i]);
steps++;
}
printf("Steps %d, index %d\n", steps, i);
return 0;
}程序输出：
Steps 4, index 11编辑:在@Raphael Miedl和@Martin Zabel的评论之后得到了改进。
Stack Overflow用户
发布于 2015-12-27 23:12:23
传统的线性搜索的一个变体可能是一个很好的方法。让我们选择一个元素，比如array[i] = 2。现在，array[i + 1]将是1或3(奇数)，array[i + 2]将是(仅限正整数)2或4(偶数)。
继续这样，可以观察到一种模式- array[i + 2*n]将包含偶数，因此所有这些索引都可以忽略。
另外，我们可以看到，
array[i + 3] = 1 or 3 or 5
array[i + 5] = 1 or 3 or 5 or 7因此，接下来应该检查索引i + 5，并且可以使用while循环来确定下一个要检查的索引，这取决于在索引i + 5处找到的值。
虽然，这具有复杂性O(n) (关于渐近复杂性的线性时间)，但在实际条件下，它比普通的线性搜索更好，因为不会访问所有的索引。
显然，如果array[i] (我们的起点)很奇怪，所有这些都会颠倒过来。
https://stackoverflow.com/questions/34481582
复制相似问题