Skuteczny sposób wyszukiwania elementu


88

Niedawno miałem wywiad, w którym zadali mi „ szukające ” pytanie.
Pytanie brzmiało:

Zakłada się, że jest tablicą (pozytywnych) całkowitymi, przy czym każdy z elementów jest albo +1czy -1w stosunku do sąsiednich elementów.

Przykład:

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

Teraz wyszukaj 7i zwróć jego pozycję.

Odpowiedziałem:

Przechowuj wartości w tymczasowej tablicy, posortuj je, a następnie zastosuj wyszukiwanie binarne.

Jeśli element zostanie znaleziony, zwróć jego pozycję w tymczasowej tablicy.
(Jeśli liczba występuje dwukrotnie, zwróć jej pierwsze wystąpienie)

Ale wydawało się, że ta odpowiedź nie zadowoliła ich.

Jaka jest właściwa odpowiedź?


4
O ile wiem, wyszukiwanie liniowe jest dobrym sposobem na zlokalizowanie indeksu elementu w tablicy. Nie jestem jeszcze pewien innego algorytmu wyszukiwania, który byłby skuteczny w lokalizowaniu indeksu elementu.
Sean Francis N. Ballais

4
Jeśli gwarantuje się, że 7 pojawi się tylko raz lub jeśli nie ma znaczenia, która 7 zostanie zwrócona, możesz jeszcze bardziej ulepszyć liniowy algorytm odpowiedzi Colemana.
user1942027

52
Jeśli Twoje oryginalne rozwiązanie wymaga sortowania, jest gorsze niż naiwne wyszukiwanie liniowe. Wydaje się, że nie jesteś tego świadomy.
cubuspl42

5
Sortowanie wymaga O (nlogn), a wyszukiwanie binarne to O (logn). Jeśli musisz przeszukać wiele, wiele wartości z dużej tablicy, twoja odpowiedź może być lepsza, ale jeśli wyszukujesz tylko raz, algorytmy O (n) mogą być lepsze.
jingyu9575

23
Nie wiem, dlaczego nikt inny o tym nie wspomniał: Wasza metoda była nie tylko nieefektywna, ale i niepoprawna , a to znacznie gorsze niż zwykła nieskuteczność. Wymaganie dotyczy pozycji podanej liczby w oryginalnej tablicy . Twoja metoda zwraca pozycję liczby w posortowanej tablicy . Teraz mógł odzyskać pierwotną pozycję, poprzez przekształcenie prostej tablicy do tablicy krotek (numer, orig_pos) przed sortowaniem. Ale o tym nie wspomniałeś, więc domyślam się, że nie wspomniałeś o tym również w wywiadzie.
Tom Zych

Odpowiedzi:


125

Możesz przeprowadzić wyszukiwanie liniowe z krokami, które są często większe niż 1. Kluczową obserwacją jest to, że jeśli np. array[i] == 4I 7 jeszcze się nie pojawiło, to następny kandydat na 7 jest pod indeksem i+3. Użyj pętli while, która wielokrotnie przechodzi bezpośrednio do następnego realnego kandydata.

Oto implementacja, nieco uogólniona. Znajduje pierwsze wystąpienie kw tablicy (z zastrzeżeniem ograniczenia + = 1) lub -1jeśli nie występuje:

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

wynik:

7 first occurs at index 11
but 9 first "occurs" at index -1

8
Dokładnie to, o czym myślałem. To O(N)prawda, ale nie sądzę, aby można było to zrobić szybciej.
shapiro yaacov

2
Mógłbyś to zrobić średnio trochę szybciej z większą liczbą kandydatów (np. Pierwszego i ostatniego), a potem iść z tym, który jest najbliżej celu - czyli wtedy, gdy potrzebujesz znaleźć tylko jedno wystąpienie, a nie pierwsze.
mkadunc

2
@mkadunc To dobry pomysł. Inną obserwacją jest to, że jeśli pierwszy i ostatni element znajdują się na odcinku 7, to w tym szczególnym przypadku możesz użyć wyszukiwania binarnego (jeśli nie obchodzi cię, które 7 znajdziesz)
John Coleman

1
W przypadku, gdy potrzebujesz znaleźć dowolną 7 (niekoniecznie pierwszą), proponuję następujące (praktyczne) ulepszenie. Zrób listę sekcji (dwie liczby całkowite, „początek” i „koniec”) i zamiast zaczynać od początku tablicy, zacznij od środka. Zgodnie z wartością w komórce zignoruj ​​odpowiedni zakres i dodaj dwie lewe sekcje do listy sekcji. Teraz powtórz dla następnej pozycji na liście. To nadal jest „O (n)”, ale za każdym razem, gdy sprawdzasz komórkę, ignorujesz dwukrotność zakresu.
shapiro yaacov

3
@ShapiroYaacov: W połączeniu ze sprawdzeniem, czy przedział od dolnej do wyższej wartości po obu stronach sekcji obejmuje k (7), zasługuje to na własną odpowiedź.
siwobrody

35

Twoje podejście jest zbyt skomplikowane. Nie musisz sprawdzać każdego elementu tablicy. Pierwsza wartość jest 4, tak 7jest przynajmniej 7-4 elementy z dala, i można pominąć tych.

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

Wyjście programu:

Steps 4, index 11

Edycja: poprawiona po komentarzach @Raphael Miedl i @Martin Zabel.


2
Dziurawiec if ((skip = 7 - array[i]) < 1) skip = 1;wydaje się zbytnio komplikować i moim zdaniem pesymizować. Jeśli array[i] == 200dostaniesz -193i po prostu przeskoczysz o 1 za każdym razem, nawet jeśli możesz pominąć wszystkie 193. Dlaczego nie po prostu i += abs(7 - array[i])?
user1942027

1
Należy ustawić skipbezwzględną różnicę między 7 a array[i].
Martin Zabel

@Raphael Miedl nie, elementu nie będzie 200, byś zdał 7.
Weather Vane

3
@WeatherVane nie mamy takiej gwarancji, tylko że sąsiednie wartości są +1/ -1od siebie. Więc może tak być, array[0] == 200a inni są w większości -1.
user1942027

1
@WeatherVane zakłada, że ​​element zawsze znajduje się w tablicy, co może nie mieć miejsca. -1 jest prawidłowym zwrotem w tym przypadku; co trochę zmienia kod, który masz
Eugene

20

Odmiana konwencjonalnego wyszukiwania liniowego może być dobrym rozwiązaniem. Wybierzmy element, powiedzmy array[i] = 2. Teraz array[i + 1]będzie 1 lub 3 (nieparzyste), array[i + 2]będzie (tylko dodatnie liczby całkowite) 2 lub 4 (liczba parzysta).

Kontynuując w ten sposób, można zaobserwować wzór - array[i + 2*n]będzie zawierał liczby parzyste, więc wszystkie te wskaźniki można zignorować.

My też to widzimy

array[i + 3] = 1 or 3 or 5
array[i + 5] = 1 or 3 or 5 or 7

tak więc indeks i + 5powinien być sprawdzony jako następny, a pętla while może być użyta do określenia następnego indeksu do sprawdzenia, w zależności od wartości znalezionej w index i + 5.

Chociaż ma to złożoność O(n)(czas liniowy pod względem złożoności asymptotycznej), w praktyce jest lepsze niż zwykłe wyszukiwanie liniowe, ponieważ nie wszystkie indeksy są odwiedzane.

Oczywiście wszystko to zostanie odwrócone, jeśli array[i](nasz punkt wyjścia) był dziwny.


8

Podejście przedstawione przez Johna Colemana jest tym, na co najprawdopodobniej liczył ankieter.
Jeśli chcesz trochę bardziej skomplikować, możesz zwiększyć oczekiwaną długość przeskoku:
wywołaj wartość docelową k . Zacznij od wartości v pierwszego elementu na pozycji p i wywołaj różnicę kv dv z wartością bezwzględną av . Aby przyspieszyć negatywne wyszukiwania, zerknij na ostatni element jako drugą wartość u na pozycji o: jeśli dv × du jest ujemne, występuje k (jeśli jakiekolwiek wystąpienie k jest dopuszczalne, możesz zawęzić zakres indeksu tutaj, tak jak robi to wyszukiwanie binarne). Jeśli av + au jest większe niż długość tablicy, k jest nieobecne. (Jeśli dv x du wynosi zero, V lub U równa k.)
Pomijając słuszność indeksu: Sonda przycisk ( „Next”) pozycja, w której sekwencja może powrócić do v k w środku: o = p + 2*av.
Jeśli dv × du jest ujemne, znajdź k (rekurencyjnie?) Od p + av do o-au;
jeśli jest równe zero, u równa się k przy o.
Jeśli du jest równe dv, a wartość w środku nie jest k, lub au przekracza av,
lub nie możesz znaleźć k od p + av do o-au,
pozwól p=o; dv=du; av=au;i kontynuuj sondowanie.
(Aby uzyskać pełny powrót do tekstów z lat 60-tych, obejrzyj je w Courier. Moją „pierwszą drugą myślą” było użycieo = p + 2*av - 1, co wyklucza du equals dv .)


4

KROK 1

Zacznij od pierwszego elementu i sprawdź, czy jest 7. Powiedzmy, że cjest to indeks aktualnej pozycji. Tak więc początkowo c = 0.

KROK 2

Jeśli jest 7, znalazłeś indeks. To jest c. Jeśli osiągnąłeś koniec tablicy, wyrwij się.

KROK 3

Jeśli tak nie jest, 7 musi znajdować się co najmniej na |array[c]-7|pozycjach dalej, ponieważ możesz dodać tylko jednostkę na indeks. Dlatego dodaj |array[c]-7|do bieżącego indeksu c i ponownie przejdź do KROKU 2, aby sprawdzić.

W najgorszym przypadku, gdy występują naprzemiennie 1 i -1, złożoność czasowa może osiągnąć O (n), ale przeciętne przypadki byłyby dostarczane szybko.


Czym to się różni od odpowiedzi Johna Colemana? (Oprócz sugerowania, |c-7|gdzie |array[c]-7|wydaje się konieczne.)
siwobrody

Właśnie zobaczyłem jego odpowiedź. Przyznaję, że główna idea jest taka sama.
Akeshwar Jha

Oryginalne pytanie nie mówi, że tablica zaczyna się od liczby mniejszej niż 7. Więc array[c]-7może być dodatnia lub ujemna. Musisz się do niego zgłosić abs()przed przejściem do przodu.
arielf

Tak, masz rację. Dlatego używam array[c] - 7z operatorem modułu, |array[c] - 7|.
Akeshwar Jha

4

Tutaj podaję implementację w 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
Nieudokumentowany kod w języku z przynajmniej półoficjalną konwencją . Czym różni się to od odpowiedzi Johna Colemana i Akeshwara, poza swobodną interpretacją znacznika „c”?
siwobrody

3

Oto rozwiązanie w stylu „dziel i rządź”. Kosztem (dużo) większej księgowości możemy pominąć więcej elementów; zamiast skanować od lewej do prawej, testuj na środku i pomijaj w obu kierunkach.

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

}

neal-fultz twoja odpowiedź nie zwróci pierwszego wystąpienia, ale dowolne przypadkowe wystąpienie elementu wyszukiwania, gdy zaczynasz od środka i przeskakujesz z dowolnej strony.
Ram Patra

Zmiana kolejności rekurencji jest pozostawiona jako ćwiczenie dla czytelnika.
Neal Fultz

1
neal-fultz, edytuj wiadomość w wywołaniu metody printf ().
Ram Patra

2

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

Chciał dołączyć rekursywne rozwiązanie problemu. Cieszyć się

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.