최근에 인터뷰를했는데 그들이 ” 검색 “질문을했습니다.
질문은 :
각 요소가 인접한 요소 중 하나
+1이거나-1비교 되는 (양수) 정수 배열이 있다고 가정 합니다.예:
array = [4,5,6,5,4,3,2,3,4,5,6,7,8];이제
7위치를 검색 하고 반환합니다.
나는이 대답을했다 :
값을 임시 배열에 저장하고 정렬 한 다음 이진 검색을 적용합니다.
요소가 발견되면 임시 배열에서 해당 위치를 반환합니다.
(번호가 두 번 발생하면 첫 번째 발생을 반환)
그러나 그들은이 답변에 만족하지 않는 것 같습니다.
정답은 무엇입니까?
답변
1보다 큰 단계로 선형 검색을 수행 할 수 있습니다. 중요한 관찰은 eg array[i] == 4와 7이 아직 나타나지 않은 경우 7에 대한 다음 후보가 index에 있다는 것 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입니다 적어도 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의 주석 이후 개선되었습니다.
답변
기존 선형 검색의 변형이 좋은 방법이 될 수 있습니다. 요소를 선택합시다 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](우리의 시작 지점)이 이상 하다면이 모든 것이 반전 될 것 입니다.
답변
John Coleman이 제시 한 접근 방식은 모든 가능성에서 면접관이 바라던 것입니다.
좀 더 복잡하게하려면 예상 건너 뛰기 길이를 늘릴 수 있습니다 .
목표 값 k를 호출합니다 . 위치 p 에서 첫 번째 요소의 값 v 로 시작하고 절대 값 av로 차이 kv dv 를 호출합니다 . 부정적인 검색 속도를 높이려면 위치 o 에서 다른 값 u 로 마지막 요소를 들여다보십시오.: dv × du가 음수이면 k가 존재합니다 (k의 발생이 허용되는 경우 여기에서 이진 검색 방식으로 인덱스 범위를 좁힐 수 있습니다). av + au가 배열의 길이보다 크면 k가 없습니다. (dvxdu가 0이면 v 또는 u는 k와 같습니다.)
인덱스 유효성 생략 : 시퀀스가 중간에 k를 사용하여 v로 돌아갈 수있는 ( “next”) 위치를 조사합니다 o = p + 2*av..
dv × du가 음수이면 p + av에서 o-au까지 k (재귀 적으로?)를 찾으십시오.
0이면 u는 o에서 k와 같습니다.
뒤이 DV 같고 중간에있는 값은 케이되지 않았거나 AU는 유명을 초과하는 경우
또는 실패 , + AV에 오 프 페이지에서 K를 찾을
수 있도록 p=o; dv=du; av=au;하고 프로빙 유지합니다.
(’60 년대 텍스트에 대한 전체 플래시백을 보려면 Courier로보기. 내 “첫 번째 두 번째 생각”은o = p + 2*av - 1, du가 dv와 같지 않음.)
답변
1 단계
첫 번째 요소로 시작하여 7인지 확인합니다 c. 현재 위치의 인덱스 라고 가정 해 보겠습니다 . 따라서 처음에는 c = 0.
2 단계
7이면 인덱스를 찾았습니다. 그것은이다 c. 배열의 끝에 도달하면 중단하십시오.
3 단계
그렇지 않은 경우 |array[c]-7|인덱스 당 하나의 단위 만 추가 할 수 있으므로 7은 최소한 떨어져 있어야합니다 . 따라서 |array[c]-7|현재 색인 c에 추가 하고 2 단계로 다시 이동하여 확인하십시오.
최악의 경우, 대체 1과 -1이있을 때 시간 복잡도는 O (n)에 도달 할 수 있지만 평균 사례는 빠르게 전달됩니다.
답변
여기에 자바 구현을 제공하고 있습니다 …
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;
}
답변
다음은 분할 및 정복 스타일 솔루션입니다. (훨씬) 더 많은 부기를 희생시키면서 더 많은 요소를 건너 뛸 수 있습니다. 왼쪽에서 오른쪽으로 스캔하는 대신 중간에서 테스트하고 양방향 으로 건너 뜁니다 .
#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;
}
