ค้นหาใน Rotated Sorted Array Leetcode Solution  


ระดับความยาก กลาง
ถามบ่อยใน อะโดบี อาลีบาบา อเมซอน แอปเปิล บลูมเบิร์ก ByteDance ซิสโก้ อีเบย์ Expedia Facebook แซคส์โกลด์แมน Google JPMorgan LinkedIn ไมโครซอฟท์ Nutanix Nvidia คำพยากรณ์ บัตรเครดิต/เดบิต หรือ PayPal Paytm Salesforce ซัมซุง ServiceNow Tencent เทสลา TripAdvisor Twitch Uber วีซ่า VMware Walmart Labs yahoo Yandex จ้า ซู่ลี่
อัลกอริทึม แถว การค้นหาแบบไบนารี การเข้ารหัส สัมภาษณ์ สัมภาษณ์เตรียม LeetCode LeetCodeSolutions

พิจารณาอาร์เรย์ที่เรียงลำดับ แต่มีการเลือกดัชนีหนึ่งรายการและอาร์เรย์ถูกหมุนที่จุดนั้น ตอนนี้เมื่ออาร์เรย์ถูกหมุนแล้วคุณจะต้องค้นหาองค์ประกอบเป้าหมายที่เฉพาะเจาะจงและส่งคืนดัชนี ในกรณีที่ไม่มีองค์ประกอบให้คืนค่า -1 โดยทั่วไปปัญหานี้เรียกว่า Search in Rotated Sorted Array Leetcode Solution ดังนั้นในคำถามนี้เราได้รับอาร์เรย์ขององค์ประกอบจำนวนเต็มบางส่วนที่เรียงลำดับและหมุนที่ดัชนีที่เราไม่รู้จัก นอกจากอาร์เรย์แล้วเรายังได้รับองค์ประกอบเฉพาะที่เราต้องการค้นหา

ค้นหาใน Rotated Sorted Array Leetcode Solution

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

คำอธิบาย: เนื่องจากองค์ประกอบที่จะค้นหาคือ 4 พบองค์ประกอบที่ดัชนี 0 เราจึงส่งคืนดัชนีของเป้าหมาย

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

คำอธิบาย: เนื่องจากองค์ประกอบไม่มีอยู่ในอาร์เรย์เราจึงคืนค่า -1

แนวทาง Brute Force สำหรับการค้นหาใน Rotated Sorted Array  

ปัญหา“ การค้นหาในอาร์เรย์เรียงลำดับแบบหมุนเวียน” ขอให้เราค้นหาดัชนีขององค์ประกอบเป้าหมายในอาร์เรย์ที่เรียงลำดับแบบหมุนที่กำหนด และเราได้พูดคุยกันแล้วว่าอาร์เรย์เรียงลำดับแบบหมุนคืออะไร? ดังนั้นวิธีที่ง่ายที่สุดที่เราคิดได้คือลอง Linear Search ในการค้นหาเชิงเส้นเราเพียงแค่สำรวจตามที่กำหนด แถว และตรวจสอบว่าองค์ประกอบปัจจุบันเป็นองค์ประกอบเป้าหมายของเราหรือไม่ หากองค์ประกอบปัจจุบันเป็นองค์ประกอบเป้าหมายเราจะส่งคืนดัชนีปัจจุบันมิฉะนั้นเราจะคืนค่า -1 วิธีการนี้ง่ายมาก แต่เนื่องจากไม่ได้ใช้ข้อเท็จจริงที่ว่าอาร์เรย์ถูกเรียงลำดับและหมุนที่ดัชนีเดียว แนวทางนี้มีความซับซ้อนของเวลาเชิงเส้น

ดูสิ่งนี้ด้วย
โซลูชัน Leetcode หมายเลข N-th Tribonacci

รหัสสำหรับการค้นหาในโซลูชัน 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)เนื่องจากเราไม่มีข้อมูลใด ๆ เกี่ยวกับแต่ละองค์ประกอบโดยเฉพาะและใช้ตัวแปรจำนวนคงที่ ดังนั้นความซับซ้อนของพื้นที่จึงคงที่

แนวทางที่เพิ่มประสิทธิภาพสำหรับการค้นหาในอาร์เรย์เรียงลำดับแบบหมุนเวียน  

แนวทางที่กล่าวถึงก่อนหน้านี้ไม่ได้ใช้ข้อเท็จจริงที่ว่าอาร์เรย์เป็นอาร์เรย์ที่เรียงลำดับแบบหมุนเวียน ดังนั้นในแนวทางนี้เราจึงพยายามใช้ข้อเท็จจริงนี้เพื่อลดความซับซ้อนของเวลา ลองพิจารณาว่าถ้าเรามีอาร์เรย์ที่จัดเรียงไว้เราจะใช้เพียงแค่ ค้นหาไบนารี แต่ในกรณีนี้ค่อนข้างยุ่งยาก นอกจากนี้เราจำเป็นต้องใช้การค้นหาแบบไบนารี แต่ถ้าเราใช้การค้นหาแบบไบนารีเราจะรู้ได้อย่างไรว่าควรเลือกส่วนใดของอาร์เรย์เมื่อเราอยู่ที่องค์ประกอบกลางของอาร์เรย์ เนื่องจากเราไม่สามารถทำตามอัลกอริทึมการค้นหาแบบไบนารีดั้งเดิมได้เนื่องจากนี่คืออาร์เรย์ที่เรียงลำดับแบบหมุนเวียน ดังนั้นจึงมีการปรับเปลี่ยนเล็กน้อยจากการค้นหาไบนารีปกติ

ดังนั้นโดยทั่วไปในการค้นหาแบบไบนารีเราจะตรวจสอบว่าองค์ประกอบปัจจุบัน (องค์ประกอบที่ดัชนีกลาง) ตรงกับเป้าหมายหรือไม่จากนั้นเราจะส่งคืนดัชนี ขั้นตอนนี้ยังคงเหมือนเดิมที่นี่ นอกจากนั้นหากไม่เหมือนกันเราจะตรวจสอบว่าเดือยอยู่ทางขวา [ขององค์ประกอบปัจจุบันหรือทางซ้าย หากอยู่ทางด้านขวาเราจะตรวจสอบว่าเป้าหมายอยู่ใน subarray ที่ไม่หมุนหรือไม่ถ้าเราอัปเดตส่วนสูงอื่น ๆ เราจะอัปเดตต่ำ ในทำนองเดียวกันถ้าเดือยอยู่ทางซ้ายเราจะตรวจสอบอีกครั้งว่าเป้าหมายอยู่ใน subarray ที่ไม่หมุนหรือไม่เราจะอัปเดตค่าต่ำมิฉะนั้นเราจะอัปเดตค่าสูง และท้ายที่สุดถ้าเราออกมาจากลูปเรามั่นใจว่าเป้าหมายนั้นไม่มีอยู่ในอาร์เรย์ที่กำหนด

ดูสิ่งนี้ด้วย
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 (บันทึก N) เนื่องจากเราใช้การค้นหาแบบไบนารีเพื่อค้นหาองค์ประกอบเป้าหมาย ความซับซ้อนของเวลาเป็นลอการิทึม

ดูสิ่งนี้ด้วย
ค้นหาความแตกต่างขั้นต่ำระหว่างสององค์ประกอบใด ๆ

ความซับซ้อนของอวกาศ

O (1), เนื่องจากเราจัดเก็บองค์ประกอบจำนวนคงที่เพียงบางส่วนเท่านั้นความซับซ้อนของพื้นที่จึงคงที่