最近我参加了一个面试,他们问了我一个“搜索性”的问题。
问题是:
假设有一个(正)整数数组,其中每个元素与其相邻元素相比要么是
+1
,要么是-1
。
示例:
array = 4,5,6,5,4,3,2,3,4,5,6,7,8;
现在搜索7
并返回其位置。
我给出了这个答案:
将这些值存储在一个临时数组中,对它们进行排序,然后应用二进制搜索。
如果找到该元素,则返回其在临时数组中的位置。
(如果该数字出现两次,则返回其第一次出现)
但是,他们似乎对这个答案并不满意。
正确的答案是什么?
发布于 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 -1
发布于 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的评论之后得到了改进。
发布于 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
复制相似问题