首页 文章

搜索元素的有效方法

提问于
浏览 次
87

最近我接受了采访，他们在那里问我一个“搜索”问题 .
问题是：

假设有一个（正）整数数组，其中每个元素与其相邻元素相比为1或-1 . 示例：array = [4,5,6,5,4,3,2,3,4,5,6,7,8];
现在搜索7并返回其位置 .

我给出了这个答案：

将值存储在临时数组中，对它们进行排序，然后应用二进制搜索 . 如果找到该元素，则返回其在临时数组中的位置 . （如果数字出现两次，则返回第一次出现）

但是，他们似乎并不满意这个答案 .

什么是正确的答案？

c arrays algorithm sorting search

7 回答

  • 34

    您可以使用通常大于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
    回复于
  • 3

    你的方法太复杂了 . 您不需要检查每个数组元素 . 第一个值是 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的评论后改进 .

    回复于
  • 8

    传统线性搜索的变体可能是一个很好的方法 . 让我们选一个元素说 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

    因此，应该检查index i + 5 ，并且可以使用while循环来确定要检查的下一个索引，具体取决于在索引 i + 5 处找到的值 .

    虽然这具有复杂度 O(n) （渐近复杂度的线性时间），但实际上它比普通线性搜索更好，因为没有访问所有索引 .

    显然，如果 array[i] （我们的起点）是奇数，所有这些都将被逆转 .

    回复于
  • 124

    John Coleman提出的方法很可能是面试官所希望的 .
    如果您愿意更复杂，可以增加预期的跳过长度：
    调用目标值k . 从位置p处的第一个元素的值v开始，并使用绝对值av调用差值k-v dv . 要加速负搜索，请查看最后一个元素作为位置o处的另一个值u：如果dv×du为负，则存在k（如果k的任何出现是可接受的，则可以在此处缩小索引范围二分搜索确实） . 如果av au大于阵列的长度，则k不存在 . （如果dv×du为零，则v或u等于k . ）
    省略索引有效性：探测序列可能返回到v的（"next"）位置，其中k位于中间： o = p + 2*av .
    如果dv×du为负，则从p av到o-au找到k（递归地？）;
    如果它为零，则u等于o .
    如果du等于dv并且中间的值不是k，或者au超过av，
    或者你没有找到从p到o-au的k，
    让 p=o; dv=du; av=au; 并继续探索 .
    （有关'60年代文本的全面回放，请使用Courier查看 . 我的"1st 2nd thought"是使用 o = p + 2*av - 1 ，这将排除du等于dv . ）

    回复于
  • 3

    STEP 1

    从第一个元素开始，检查它是否's 7. Let'表示 c 是当前位置的索引 . 所以，最初， c = 0 .

    STEP 2

    如果是7，则找到索引 . 这是 c . 如果你已经到达阵列的末尾，那么就爆发了 .

    STEP 3

    如果不是，则7必须至少离开 |array[c]-7| 个位置，因为每个索引只能添加一个单位 . 因此，将 |array[c]-7| 添加到当前索引c，然后再次转到步骤2进行检查 .

    在最坏的情况下，当存在交替的1和-1时，时间复杂度可能达到O（n），但是平均情况将快速传递 .

    回复于
  • 20

    这里我给出了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;
}
    回复于
  • 2

    这是一种分而治之的风格解决方案 . 以（更多）簿记为代价，我们可以跳过更多元素;而不是从左向右扫描，在中间测试并在两个方向上跳过 .

    #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;                                                                     

}
    回复于

相关问题