搜索旋轉排序的數組Leetcode解決方案  


難度級別 中烘焙
經常問 土磚 阿里巴巴 亞馬遜 蘋果 彭博社 ByteDance 思科 易趣 Expedia的 Facebook 高盛 谷歌 摩根大通 LinkedIn Microsoft微軟 Nutanix Nvidia公司 神諭 貝寶 Paytm Salesforce的 Samsung 的ServiceNow 騰訊 特斯拉 到到網 Twitch 尤伯杯 簽證 VMware的 沃爾瑪實驗室 雅虎 Yandex的 Zillow的 Zulily
算法 排列 二元搜尋 編碼 訪問 面試準備 力碼 力碼解決方案

考慮一個排序的數組,但是選擇了一個索引,然後在該點旋轉了數組。 現在,旋轉數組後,您需要找到特定的目標元素並返回其索引。 如果該元素不存在,則返回-1。 該問題通常稱為“在旋轉排序的陣列Leetcode解決方案中搜索”。 因此,在這個問題中,我們提供了一些整數元素的數組,這些元素按我們不知道的特定索引進行排序和旋轉。 除了數組,我們還需要找到一個特定的元素。

搜索旋轉排序的數組Leetcode解決方案

array: [4,5,6,7,0,1,2]
target: 4

說明:由於要搜索的元素為4。該元素位於索引0處,因此我們返回目標的索引。

array: [4,5,6,7,0,1,2]
target: 3
-1

說明:由於該元素不存在於數組中,因此我們返回-1。

旋轉排序數組中的蠻力搜索方法  

問題“在旋轉排序數組中搜索”要求我們在給定的旋轉排序數組中找到目標元素的索引。 我們已經討論了什麼是旋轉排序數組? 因此,人們可以想到的最簡單的方法是嘗試線性搜索。 在線性搜索中,我們只需遍歷給定 排列 並檢查當前元素是否是我們的目標元素。 如果當前元素是目標元素,則返回當前索引,否則返回-1。 該方法非常簡單,但是由於它沒有使用數組按單個索引排序和旋轉的事實。 這種方法具有線性時間複雜度。

也可以看看
第N個Tribonacci號碼Leetcode解決方案

旋轉排序數組Leetcode解決方案中的搜索代碼

C ++代碼

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

int search(vector<int>& nums, int target) {
    int n = nums.size();
    for(int i=0;i<n;i++)
        if(nums[i] == target)
            return i;
    return -1;
}

int main(){
    vector<int> nums({4,5,6,7,0,1,2});
    cout<<search(nums, 4);
}

Java代碼

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static int search(int[] nums, int target) {
        int n = nums.length;
        for(int i=0;i<n;i++)
            if(nums[i] == target)
                return i;
        return -1;
    }
    
    public static void main(String[] args){
    	int nums[] = {4,5,6,7,0,1,2};
    	System.out.println(search(nums, 4));
    }
}

複雜度分析

時間複雜度

上), 因為在最壞的情況下,目標元素可能會出現在數組的末尾。 因此,時間複雜度是線性的。

空間複雜度

O(1),因為我們沒有關於每個元素的具體信息,並且使用了恆定數量的變量。 因此,空間複雜度是恆定的。

旋轉排序數組中的優化搜索方法  

前面提到的方法沒有使用數組是旋轉排序數組的事實。 因此,在這種方法中,我們嘗試利用這一事實來減少時間複雜度。 考慮一下,如果我們有一個排序的數組,我們會簡單地使用 二進制搜索 但是萬一這有點棘手。 在這裡,我們還需要使用二進制搜索。 但是,如果我們使用二進制搜索,那麼一旦進入數組的中間元素,我們如何知道要選擇數組的哪一部分呢? 因為我們不能簡單地遵循原始的二進制搜索算法,因為這是一個旋轉的排序數組。 因此,對常規的二進制搜索進行了一些修改。

因此,通常在二進制搜索中,我們檢查當前元素(中間索引處的元素)是否與目標相同,然後返回其索引。 此步驟在此保持不變。 除此之外,如果它們不相同,我們將檢查樞軸是否位於[當前元素的右側]或左側。 如果它位於右邊,則我們檢查目標是否位於非旋轉子數組中,如果它確實更新了高點,否則我們更新了低點。 同樣,如果樞軸位於左側,則再次檢查目標是否位於非旋轉子數組中,我們更新低點,否則我們更新高點。 最後,如果我們退出循環,則可以確保目標不存在於給定數組中。

也可以看看
Sqrt(x)Leetcode解決方案

旋轉排序數組Leetcode解決方案中用於搜索的優化代碼

C ++代碼

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

int search(vector<int>& nums, int target) {
    int n = nums.size();
    int low = 0, high = n-1;
    while(low<=high){
        int mid = (low+high)/2;
        // check if the current element is target
        if(nums[mid] == target)
            return mid;
        // if the starting index of the search space has smaller element than current element
        else if(nums[low]<=nums[mid]){
            // if target lies in non-rotated search space (or subarray)
            if(target >= nums[low] && target < nums[mid])
                high = mid - 1;
            else
                low = mid + 1;
        } else {
            // if target lies in non-rotated subarray
            if(target>nums[mid] && target<=nums[high])
                low = mid + 1;
            else
                high = mid - 1;
        }
    }
    // if you couldn't find the target element until now then it does not exists
    return -1;
}
int main(){
    vector<int> nums({4,5,6,7,0,1,2});
    cout<<search(nums, 4);
}

Java代碼

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static int search(int[] nums, int target) {
        int n = nums.length;
        int low = 0, high = n-1;
        while(low<=high){
            int mid = (low+high)/2;
            // check if the current element is target
            if(nums[mid] == target)
                return mid;
            // if the starting index of the search space has smaller element than current element
            else if(nums[low]<=nums[mid]){
                // if target lies in non-rotated search space (or subarray)
                if(target >= nums[low] && target < nums[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            } else {
                // if target lies in non-rotated subarray
                if(target>nums[mid] && target<=nums[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        // if you couldn't find the target element until now then it does not exists
        return -1;
    }
    
    public static void main(String[] args){
    	int nums[] = {4,5,6,7,0,1,2};
    	System.out.println(search(nums, 4));
    }
}

複雜度分析

時間複雜度

O(log N), 因為我們已經使用二進制搜索來找到目標元素。 時間複雜度是對數的。

也可以看看
找出任何兩個元素之間的最小差異

空間複雜度

O(1), 由於我們僅存儲了一定數量的元素,因此空間複雜度是恆定的。