search元素的有效方法
最近我接受了一个采访，他们问我一个“ 寻找 ”的问题。
问题是：
假设有一个（正）整数数组，其中每个元素与其相邻元素相比是
+1或-1。例：
array = [4,5,6,5,4,3,2,3,4,5,6,7,8];现在search
7并返回其位置。
我给了这个答案：
将值存储在临时数组中，对其进行sorting，然后应用二进制search。
如果find该元素，则将其位置返回到临时数组中。
（如果数字发生两次，则返回其第一次出现）
但是，他们似乎不满意这个答案。
什么是正确的答案？
你可以用大于1的步进行线性search。关键的观察是，如果例如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
你的方法太复杂了。 您不需要检查每个数组元素。 第一个值是4 ，所以7 至less有 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的评论。
传统的线性search的一个变种可能是一个好方法。 让我们选一个元素，说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处find的值。
虽然复杂度为O(n) （线性时间就渐近复杂度而言），但由于所有的指标都没有被访问，所以它比一般的线性search更实用。
显然，如果array[i] （我们的出发点）是奇数的话，所有这些都将被逆转。
约翰·科尔曼（John Coleman）提出的方法就是面试者所希望的。
如果你愿意变得更复杂一些，你可以增加预期的跳跃长度：
调用目标值k 。 从位置p的第一个元素的值v开始，用绝对值av调用差值kv dv 。 为了加速负面search，在最后一个元素上查看位置o处的另一个值u ：如果dv×du是负数，则存在k（如果出现k是可接受的，那么您可以在这里缩小索引范围二进制search）。 如果av + au大于数组的长度，则k不存在。 （如果dv×du是零，v或u等于k。）
省略索引有效性：在中间探测序列可能返回到v的（“下一个”）位置： o = p + 2*av 。
如果dv×du是负数，则从p + av到o-aufindk（recursion？）;
如果它是零，则u等于o。
如果du等于dv并且中间的值不是k，或者au超过av，
或者你没有findk从p + av到o-au，
让p=o; dv=du; av=au; p=o; dv=du; av=au; 并继续探究。
（对于60年代的全文，用Courier查看，我的“1st 2nd thought”是使用o = p + 2*av - 1 ，这就排除了du等于dv 。
步骤1
从第一个元素开始，检查它是否为7.假设c是当前位置的索引。 所以，最初， c = 0 。
第2步
如果是7，你find了索引。 这是c 。 如果你已经到了数组的末尾，那就打个比方吧。
第3步
如果不是，那么7必须是最小的|array[c]-7| 因为您只能为每个索引添加一个单位，因此将其定位。 所以Add |array[c]-7| 到您当前的索引c，然后再次进入步骤2检查。
在最坏的情况下，当有replace1和-1时，时间复杂度可能达到O（n），但是平均情况会很快传递。
在这里，我正在给java的实施…
public static void main(String[] args) { int arr[]={4,5,6,5,4,3,2,3,4,5,6,7,8}; int pos=searchArray(arr,7); if(pos==-1) System.out.println("not found"); else System.out.println("position="+pos); } public static int searchArray(int[] array,int value) { int i=0; int strtValue=0; int pos=-1; while(i<array.length) { strtValue=array[i]; if(strtValue<value) { i+=value-strtValue; } else if (strtValue==value) { pos=i; break; } else { i=i+(strtValue-value); } } return pos; }
这是一个分而治之的风格解决scheme。 以更多的簿记为代价，我们可以跳过更多的元素; 而不是从左到右扫描，在中间testing并跳过两个方向。
#include <stdio.h> #include <math.h> int could_contain(int k, int left, int right, int width); int find(int k, int array[], int lower, int upper); 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",find(7,a,0,14)); printf("but 9 first \"occurs\" at index %d\n",find(9,a,0,14)); return 0; } int could_contain(int k, int left, int right, int width){ return (width >= 0) && (left <= k && k <= right) || (right <= k && k <= left) || (abs(k - left) + abs(k - right) < width); } int find(int k, int array[], int lower, int upper){ //printf("%d\t%d\n", lower, upper); if( !could_contain(k, array[lower], array[upper], upper - lower )) return -1; int mid = (upper + lower) / 2; if(array[mid] == k) return mid; lower = find(k, array, lower + abs(k - array[lower]), mid - abs(k - array[mid])); if(lower >= 0 ) return lower; upper = find(k, array, mid + abs(k - array[mid]), upper - abs(k - array[upper])); if(upper >= 0 ) return upper; return -1; }
