Эргэгдсэн эрэмбэлэгдсэн массивын Leetcode шийдэлээс хайх  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Adobe Alibaba Амазоны Apple-ийн Bloomberg БайтДанс Cisco Ebay Expedia Facebook-ийн Goldman Sachs Google-ийн JPMorgan LinkedIn Microsoft- Nutanix Nvidia Oracle-ийн PayPal Paytm Борлуулалтын хүч Samsung ҮйлчилгээNow Tencent Tesla TripAdvisor чангаах Uber Виз VMware Walmart лабораторууд Yahoo Yandex Зиллоу Зулили
алгоритмууд Array Хоёртын хайлт кодлох ярилцлага ярилцлагын бэлтгэл LeetCode LeetCodeSolutions

Эрэмбэлэгдсэн массивыг авч үзье, гэхдээ нэг индексийг сонгоод тэр үед массивыг эргүүлэв. Одоо массивыг эргүүлсний дараа тодорхой зорилтот элементийг олж индексийг буцааж өгөх шаардлагатай байна. Хэрэв элемент байхгүй бол буцаана -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 буцаана.

Эргүүлсэн эрэмбэлсэн массиваас хайхад хүргэх хүчирхийллийн хүч  

"Эргэгдсэн эрэмбэлэгдсэн массиваар хайх" гэсэн асуудал нь тухайн эргүүлсэн эрэмбэлэгдсэн массив дахь зорилтот элементийн индексийг олохыг биднээс хүсдэг. Эргүүлсэн эрэмбэлэгдсэн массив гэж юу болох талаар бид аль хэдийн ярилцсан уу? Тиймээс бодож болох хамгийн энгийн арга бол Шугаман хайлтыг туршиж үзэх явдал юм. Шугаман хайлтанд бид өгөгдсөн зүйлийг л тойрон гардаг массив мөн одоогийн элемент нь бидний зорилтот элемент мөн эсэхийг шалгана уу. Хэрэв одоогийн элемент нь зорилтот элемент бол бид одоогийн индексийг буцааж өгөх болно. Энэ хандлага нь маш энгийн боловч массивыг нэг индексээр эрэмбэлж, эргүүлдэг гэдгийг ашигладаггүй тул хандлага нь маш энгийн байдаг. Энэхүү арга нь цаг хугацааны шугаман нарийн төвөгтэй байдаг.

мөн үзнэ үү
N-th 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 (N), Учир нь хамгийн муу тохиолдолд зорилтот элемент нь массивын төгсгөлд байж болно. Тиймээс цаг хугацааны нарийн төвөгтэй байдал нь шугаман юм.

Сансрын нарийн төвөгтэй байдал

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 (бүртгэл N), Зорилтот элементийг олохын тулд бид хоёртын хайлтыг ашигласан тул. Цаг хугацааны нарийн төвөгтэй байдал нь логарифм юм.

мөн үзнэ үү
Хоёр элементийн хоорондох хамгийн бага ялгааг олох

Сансрын нарийн төвөгтэй байдал

O (1), бид зөвхөн зарим тооны тогтмол тооны элементүүдийг хадгалдаг тул орон зайн нарийн төвөгтэй байдал тогтмол байдаг.