Wyszukaj element w posortowanej tablicy obróconej

Poziom trudności Średni
Często zadawane pytania Adobe Amazonka Apple Bloomberg ByteDance eBay Expedia Facebook Google Microsoft Nvidia wyrocznia PayPal Paytm VMware Laboratoria Walmart Zillow
Szyk Wyszukiwanie binarneodwiedzajacy 63

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

W wyszukiwaniu posortowane obrócone szyk problem podaliśmy posortowaną i obróconą tablicę oraz element, sprawdź czy dany element występuje w tablicy czy nie.

Przykłady

Wkład
nums [] = {2, 5, 6, 0, 0, 1, 2}
cel = 0
Wydajność
prawdziwy

Wyszukaj element w posortowanej tablicy obróconejszpilka

Wkład
nums [] = {2, 5, 6, 0, 0, 1, 2}
cel = 3
Wydajność
fałszywy

Naiwne podejście do wyszukiwania elementu w posortowanej, obróconej tablicy

Przechodzenie liniowo w tablicy i wyszukiwanie wartości docelowej.

  1. Uruchom pętlę dla i = 0 do n (brak w zestawie), gdzie n to liczba elementów w tablicy.
  2. W każdej iteracji sprawdź, czy liczba [i] jest równa wartości docelowej, czy nie. Jeśli jest równa, zwróć true, w przeciwnym razie kontynuuj dla następnego elementu.
  3. Jeśli nie ma elementu równego wartości docelowej, zwróć false.

Kod JAVA

public class SearchInRotatedAndSortedArray {
    private static boolean searchTarget(int[] nums, int target) {
        int n = nums.length;
        // Traverse the given array and search for the target value
        for (int i = 0; i < n; i++) {
            if (nums[i] == target) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{2, 5, 6, 0, 0, 1, 2};
        int target = 0;

        System.out.println(searchTarget(nums, target));

        // Example 2
        target = 3;

        System.out.println(searchTarget(nums, target));
    }
}
true
false

Kod C ++

#include<bits/stdc++.h> 
using namespace std;

bool searchTarget(int *nums, int target, int n) {
    // Traverse the given array and search for the target value
    for (int i = 0; i < n; i++) {
        if (nums[i] == target)
            return true;
    }
    return false;
}

int main() {
    // Example 1
    int nums[] = {2, 5, 6, 0, 0, 1, 2};
    int target = 0;
    int n = sizeof(nums) / sizeof(nums[0]);
    
    if (searchTarget(nums, target, n)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    target = 3;
    
    if (searchTarget(nums, target, n)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
true
false

Analiza złożoności wyszukiwania elementu w posortowanej, obróconej tablicy

Złożoność czasowa = Na)
Złożoność przestrzeni = O (1) 
gdzie n to liczba elementów w tablicy.

Optymalne podejście do wyszukiwania elementu w posortowanej, obróconej tablicy

Tablica może zawierać duplikaty, więc pomysł podzielenia tablicy na dwie posortowane tablice nie zadziała.

Niech początkowym indeksem tablicy będzie l, a końcowym indeksem h,

  1. Znajdź środek, jako mid = (l + h) / 2.
  2. Jeśli argument arr [mid] jest równy wartości docelowej, zwraca wartość true.
  3. Jeśli arr [l] jest równe arr [h] jest równe arr [mid], wówczas zwiększaj l i zmniejszaj h.
  4. W przeciwnym razie, jeśli arr [l] jest mniejsze lub równe arr [mid], to lewa połowa jest sortowana, jeśli cel leży w zakresie posortowanej lewej połowy, szukaj w lewej połowie, w przeciwnym razie szukaj w prawej połowie.
  5. Jeśli powyższy warunek nie jest spełniony, sortowana jest prawa połowa, od środka do h, jeśli cel leży w zakresie posortowanej prawej połowy, szukaj w prawej połowie, w przeciwnym razie szukaj w lewej połowie.

Kod JAVA

public class SearchInRotatedAndSortedArray {
    private static boolean searchTarget(int[] nums, int target, int l, int h) {
        // Index out of bound, element does not exist
        if (l > h)
            return false;
        // Find the middle element
        int mid = (l + h) / 2;
        // If this is the target element, return true
        if (nums[mid] == target) {
            return true;
        }
        // If nums[l] = nums[h] = nums[mid], increment l and decrement h
        if (nums[l] == nums[mid] && nums[h] == nums[mid]) {
            return searchTarget(nums, target, l + 1, h - 1);
        }
        
        // If nums[l] <= nums[mid], left half is sorted
        if (nums[l] <= nums[mid]) {
            // If the target lies in the first half, search in first half
            if (target >= nums[l] && target <= nums[mid]) {
                return searchTarget(nums, target, l, mid - 1);
            }
            // Else search in second half
            return searchTarget(nums, target, mid + 1, h);
        }
        
        // If first half is not sorted, then second half is sorted
        // If the target is present in the second half, search in second half
        if (target >= nums[mid] && target <= nums[h]) {
            return searchTarget(nums, target, mid + 1, h);
        }
        // Else search in the first half
        return searchTarget(nums, target, l, mid - 1);
    }
    
    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{2, 5, 6, 0, 0, 1, 2};
        int target = 0;
        
        System.out.println(searchTarget(nums, target, 0, nums.length - 1));
        
        // Example 2
        target = 3;

        System.out.println(searchTarget(nums, target, 0, nums.length - 1));
    }
}
true
false

Kod C ++

#include<bits/stdc++.h> 
using namespace std;

bool searchTarget(int *nums, int target, int l, int h) {
    // Index out of bound, element does not exist
    if (l > h)
        return false;
    // Find the middle element
    int mid = (l + h) / 2;
    // If this is the target element, return true
    if (nums[mid] == target)
        return true;
    // If nums[l] = nums[h] = nums[mid], increment l and decrement h
    if (nums[l] == nums[mid] && nums[h] == nums[mid]) {
        return searchTarget(nums, target, l + 1, h - 1);
    }
    
    // If nums[l] <= nums[mid], left half is sorted
    if (nums[l] <= nums[mid]) {
        // If the target lies in the first half, search in first half
        if (target >= nums[l] && target <= nums[mid]) {
            return searchTarget(nums, target, l, mid - 1);
        }
        // Else search in second half
        return searchTarget(nums, target, mid + 1, h);
    }

    // If first half is not sorted, then second half is sorted
    // If the target is present in the second half, search in second half
    if (target >= nums[mid] && target <= nums[h]) {
        return searchTarget(nums, target, mid + 1, h);
    }
    // Else search in the first half
    return searchTarget(nums, target, l, mid - 1);
}

int main() {
    // Example 1
    int nums[] = {2, 5, 6, 0, 0, 1, 2};
    int target = 0;
    int n = sizeof(nums) / sizeof(nums[0]);
    
    if (searchTarget(nums, target, 0, n - 1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    target = 3;
    
    if (searchTarget(nums, target, 0, n - 1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
true
false

Analiza złożoności wyszukiwania elementu w posortowanej, obróconej tablicy

Złożoność czasowa = O (log n)
Złożoność przestrzeni = O (1) 
gdzie n to liczba elementów w tablicy.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »