요소를 효율적으로 검색하는 방법

요소를 효율적으로 검색하는 방법

최근에 저는 인터뷰를 했는데, 그들은 저에게 "찾아보는" 질문을 했습니다.
을 사용하다

(정수가 되어 있고, 그중각가 (양수)로 되어 합니다.+1 ★★★★★★★★★★★★★★★★★」-1그 인접 요소들과 비교합니다.

예:

array = [4,5,6,5,4,3,2,3,4,5,6,7,8];

,.7제자리로 돌아가다.

나는 다음과 같은 대답을 했다.

값을 임시 배열에 저장하고 정렬한 다음 이진 검색을 적용합니다.

요소가 발견되면 임시 배열에서 해당 위치를 반환합니다.
가 두 번 첫 번호를 (번호가 두 번 발생할 경우 첫 번째 번호를 반환합니다.)

하지만 그들은 이 대답에 만족하지 않는 것 같았다.

정답은 무엇일까요?

종종 1보다 큰 단계를 사용하여 선형 검색을 수행할 수 있습니다.이치하다array[i] == 4입니다.i+3고리를 틀다

여기 구현이 있습니다.이치노은 첫 을 발견한다.k 내(+=1 ) (+=1 제한에 해당)-1"CHANGE: " "CHANGE: "CHANGE:

#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

const findMeAnElementsFunkyArray = (arr, ele, i) => {
  const elementAtCurrentIndex = arr[i];

  const differenceBetweenEleAndEleAtIndex = Math.abs(
    ele - elementAtCurrentIndex
  );

  const hop = i + differenceBetweenEleAndEleAtIndex;

  if (i >= arr.length) {
    return;
  }
  if (arr[i] === ele) {
    return i;
  }

  const result = findMeAnElementsFunkyArray(arr, ele, hop);

  return result;
};

const array = [4,5,6,5,4,3,2,3,4,5,6,7,8];

const answer = findMeAnElementsFunkyArray(array, 7, 0);

console.log(answer);

문제에 대한 재귀적 해결책을 포함시키고 싶었다.즐거운 시간 되세요.

순서 1

. '우리'라고 합시다.c현재 위치의 색인입니다. 처음에는 '아예'라고 합니다c = 0.

순서 2

입니다.7이치노입니다.c어레이의 끝에 도달한 경우 탈출합니다.

순서 3

않은 7이어야 .|array[c]-7|인덱스당 단위만 추가할 수 있으므로 위치가 멀어집니다.[Add(추가)]를 합니다.|array[c]-7|현재 인덱스 c로 이동한 후 다시 스텝 2로 이동하여 확인합니다.

최악의 경우, 대체 1과 -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;
}

당신의 접근법은 너무 복잡해요.모든 어레이 요소를 검사할 필요는 없습니다. 번째 은 " " " 입니다.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

편집: @Martin Zabel의 코멘트 후 개선되었습니다.

다음은 분할 및 정복 방식의 솔루션입니다.더 많은 부기를 사용하는 대신 더 많은 요소를 건너뛸 수 있습니다. 왼쪽에서 오른쪽으로 스캔하는 것이 아니라 중간에서 테스트하고 양방향으로 건너뜁니다.

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

}

기존의 선형 검색을 변형하는 것이 좋은 방법이 될 수 있습니다.다음 요소를 선택합니다.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 loop을 사용하여 인덱스에서 발견된 값에 따라 체크할 다음 인덱스를 결정할 수 있습니다.i + 5.

한편, 이것은 복잡성이 있습니다.O(n)(점근 복잡도 측면에서 선형 시간), 모든 지수를 방문하지 않기 때문에 실질적인 측면에서 일반적인 선형 검색보다 낫다.

분명히 이 모든 것이 뒤바뀌게 될 것이다.array[i](우리의 출발점은) 이상했다.

존 콜먼이 제시한 접근법은 면접관이 희망했던 접근법일 가능성이 높습니다.
좀 더 복잡한 경우 예상되는 건너뛰기 길이를 늘릴 수 있습니다.
목표값 k를 호출합니다.위치 p에서 첫 번째 요소의 값 v에서 시작하여 절대값 av를 사용하여 차이 k-v dv를 호출합니다.네거티브 검색 속도를 높이려면 마지막 요소를 위치 o의 다른 값 u로 살펴봅니다. dv×du가 음수이면 k가 존재합니다(k의 발생이 허용 가능한 경우 여기서 바이너리 검색 방식으로 인덱스 범위를 좁힐 수 있습니다).av+au가 배열 길이보다 크면 k가 없습니다(dv×du가 0이면 v 또는 u는 k).
유효성 : 시퀀스가 v로 수("를 프로브합니다: "next"는 "next"입니다.o = p + 2*av.
이면 pdv×du로 k.
는 oo o o .
k가 av를 하는 경우 du' dv'는 av'k'au' av'입니다.
또는 p+av에서 o-au까지 k를 찾을 수 없습니다.
를 놓다p=o; dv=du; av=au;계속 조사해봐
(60ies 문자에 대한 전체 플래시백은 Courier에서 확인하십시오. 번째 두 은 '두 번째 생각'을 요.o = p + 2*av - 1du는 dv가 되지 않습니다.)

언급URL : https://stackoverflow.com/questions/34481582/efficient-way-to-search-an-element