요소를 효율적으로 검색하는 방법
최근에 인터뷰를했는데 그들은 " 검색 "질문을했습니다.
질문은 :
각 요소가 인접한 요소 중 하나
+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의 의견 이후 개선되었습니다.
A variation of the conventional linear search could be a good way to go. Let us pick an element say array[i] = 2
. Now, array[i + 1]
will either be 1 or 3 (odd), array[i + 2]
will be (positive integers only) 2 or 4 (even number).
On continuing like this, a pattern is observable - array[i + 2*n]
will hold even numbers and so all these indices can be ignored.
Also, we can see that
array[i + 3] = 1 or 3 or 5
array[i + 5] = 1 or 3 or 5 or 7
so, index i + 5
should be checked next and a while loop can be used to determine the next index to check, depending on the value found at index i + 5
.
While, this has complexity O(n)
(linear time in terms of asymptotic complexity), it is better than a normal linear search in practical terms as all the indices are not visited.
Obviously, all this will be reversed if array[i]
(our starting point) was odd.
The approach presented by John Coleman is what the interviewer was hoping for, in all probability.
If you are willing to go quite a bit more complicated, you can increase expected skip length:
Call the target value k. Start with the first element's value v at position p and call the difference k-v dv with absolute value av. To speed negative searches, have a peek at the last element as the other value u at position o: if dv×du is negative, k is present (if any occurrence of k is acceptable, you may narrow down the index range here the way binary search does). If av+au is greater than the length of the array, k is absent. (If dv×du is zero, v or u equals k.)
Omitting index validity: Probe the ("next") position where the sequence might return to v with k in the middle: o = p + 2*av
.
If dv×du is negative, find k (recursively?) from p+av to o-au;
if it is zero, u equals k at o.
If du equals dv and the value in the middle isn't k, or au exceeds av,
or you fail to find k from p+av to o-au,
let p=o; dv=du; av=au;
and keep probing.
(For a full flash-back to '60ies texts, view with Courier. My "1st 2nd thought" was to use o = p + 2*av - 1
, which precludes du equals dv.)
STEP 1
Start with the first element and check if it's 7. Let's say c
is the index of the current position. So, initially, c = 0
.
STEP 2
If it is 7, you found the index. It's c
. If you've reached the end of the array, break out.
STEP 3
If it's not, then 7 must be atleast |array[c]-7|
positions away because you can only add a unit per index. Therefore, Add |array[c]-7|
to your current index, c, and go to STEP 2 again to check.
In the worst case, when there are alternate 1 and -1s, the time complexity may reach O(n), but average cases would be delivered quickly.
Here I am giving the implementation in 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;
}
Here is a divide-and-conquer style solution. At the expense of (much) more bookkeeping, we can skip more elements; rather than scanning left-to-right, test in the middle and skip in both directions.
#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;
}
참고URL : https://stackoverflow.com/questions/34481582/efficient-way-to-search-an-element
'program story' 카테고리의 다른 글
"인수 목록이 너무 길다"는 경우 3 일이 지난 모든 파일을 삭제하는 방법은 무엇입니까? (0) | 2020.09.09 |
---|---|
Swift 하위 클래스 UIView (0) | 2020.09.09 |
명령이 완료 될 때까지 기다리지 않고 shell_exec를 사용하는 방법이 있습니까? (0) | 2020.09.09 |
자바 스크립트 변수 참조 / 별칭 (0) | 2020.09.09 |
자바 스크립트 중첩 함수 (0) | 2020.09.09 |