ស្វែងរកនៅក្នុងដំណោះស្រាយវិលអារេ Leetcode


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Alibaba ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ទីភ្នាក់ងារ Bloomberg ByteDance ស៊ីស្កូ របស់ eBay Expedia Facebook ក្រុមហ៊ុន Goldman Sachs ក្រុមហ៊ុន google ក្រុមហ៊ុន JPMorgan LinkedIn ក្រុមហ៊ុន Microsoft ផ្លែល្ហុង nvidia បាន ក្រុមហ៊ុន Oracle បានតាមរយៈការ Paytm ការលក់ ក្រុមហ៊ុន Samsung ServiceNow ។ ក្រុមហ៊ុន Tencent ក្រុមហ៊ុន tesla TripAdvisor Twitch Uber ទិដ្ឋាការ VMware បន្ទប់ពិសោធន៍វ៉លម៉ាត ក្រុមហ៊ុន Yahoo Yandex Zillow ហ្ស៊ូលី
អារេ ការស្វែងរកគោលពីរ

ពិចារណាអារេដែលបានតម្រៀបប៉ុន្តែសន្ទស្សន៍មួយត្រូវបានជ្រើសរើសហើយអារេត្រូវបានបង្វិលនៅចំណុចនោះ។ ឥឡូវនៅពេលដែលអារេត្រូវបានបង្វិលអ្នកត្រូវរកធាតុគោលដៅជាក់លាក់មួយហើយត្រឡប់សន្ទស្សន៍របស់វា។ ក្នុងករណីដែលធាតុមិនមានវត្តមានត្រលប់មកវិញ -១ ។ បញ្ហានេះត្រូវបានគេសំដៅជាទូទៅថាជាការស្វែងរកនៅក្នុងដំណោះស្រាយវិលអារេ Leetcode ។ ដូច្នេះនៅក្នុងសំណួរយើងត្រូវបានផ្តល់ជូននូវអារេនៃធាតុអាំងតេក្រាលមួយចំនួនដែលត្រូវបានតម្រៀបនិងបង្វិលនៅលិបិក្រមជាក់លាក់មួយដែលយើងមិនស្គាល់។ រួមជាមួយអារេយើងក៏ត្រូវបានផ្តល់នូវធាតុជាក់លាក់មួយដែលយើងត្រូវរក។

ស្វែងរកនៅក្នុងដំណោះស្រាយវិលអារេ Leetcode

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

ការពន្យល់ៈដោយសារធាតុដែលត្រូវស្វែងរកគឺ ៤. ធាតុត្រូវបានរកឃើញនៅសន្ទស្សន៍ ០ យើងត្រឡប់សន្ទស្សន៍គោលដៅ។

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

ការពន្យល់ៈដោយសារធាតុមិនមាននៅក្នុងជួរយើងត្រឡប់ -1 ។

វិធីសាស្រ្តរបស់ Brute Force សម្រាប់ការស្វែងរកនៅក្នុងការបង្វិលតម្រៀបអារេ

បញ្ហា“ ស្វែងរកនៅក្នុងវេនវិលអារេ” ស្នើឱ្យយើងរកលិបិក្រមនៃធាតុគោលដៅនៅក្នុងជួរដែលបានតម្រៀបដែលបានបង្វិល។ ហើយយើងបានពិភាក្សារួចហើយថាអារេបង្វិលតម្រៀបគ្នាជាអ្វី? ដូច្នេះវិធីសាស្រ្តសាមញ្ញបំផុតដែលមនុស្សម្នាក់អាចគិតគឺសាកល្បងលីនេអ៊ែរស្វែងរក។ នៅក្នុងលីនេអ៊ែរស្វែងរកយើងឆ្លងកាត់អ្វីដែលបានផ្តល់ឱ្យ អារេ និងពិនិត្យមើលថាតើធាតុបច្ចុប្បន្នគឺជាធាតុគោលដៅរបស់យើង។ ប្រសិនបើធាតុបច្ចុប្បន្នគឺជាធាតុគោលដៅយើងត្រលប់មកវិញនូវសន្ទស្សន៍បច្ចុប្បន្នដែលយើងត្រលប់មកវិញ -១ ។ វិធីសាស្រ្តគឺសាមញ្ញណាស់ប៉ុន្តែដោយសារវាមិនប្រើការពិតដែលថាអារេត្រូវបានតម្រៀបនិងបង្វិលនៅសន្ទស្សន៍តែមួយ។ វិធីសាស្រ្តនេះមានភាពស្មុគស្មាញពេលវេលាលីនេអ៊ែរ។

លេខកូដសំរាប់ស្វែងរកក្នុងវេនដំណោះស្រាយអារេ 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);
}
0

ចាវ៉ាកូដ

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

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (N), ពីព្រោះក្នុងករណីដែលអាក្រក់បំផុតធាតុគោលដៅអាចមានវត្តមាននៅខាងចុងជួរអារេ។ ដូច្នេះពេលវេលាស្មុគស្មាញគឺលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១)ដោយសារយើងមិនមានព័ត៌មានទាក់ទងនឹងធាតុនីមួយៗជាពិសេសហើយបានប្រើចំនួនថេរនៃអថេរ។ ដូច្នេះភាពស្មុគស្មាញនៃលំហគឺថេរ។

វិធីសាស្រ្តប្រសើរបំផុតសម្រាប់ការស្វែងរកនៅក្នុងការបង្វិលតម្រៀបអារេ

វិធីសាស្រ្តដែលបានលើកឡើងពីមុនមិនបានប្រើការពិតដែលថាអារេគឺជាអារេបង្វិលតម្រៀប។ ដូច្នេះនៅក្នុងវិធីសាស្រ្តនេះយើងព្យាយាមប្រើការពិតនេះដើម្បីកាត់បន្ថយពេលវេលាស្មុគស្មាញ។ ពិចារណាប្រសិនបើយើងមានអារេតម្រៀបយើងនឹងត្រូវបានប្រើយ៉ាងសាមញ្ញ ការស្វែងរកគោលពីរ ប៉ុន្តែក្នុងករណីនេះជាល្បិចកលបន្តិច។ នៅទីនេះយើងត្រូវបានគេតម្រូវឱ្យប្រើការស្វែងរកគោលពីរ។ ប៉ុន្តែប្រសិនបើយើងប្រើការស្វែងរកគោលពីរតើធ្វើដូចម្តេចដើម្បីដឹងថាតើផ្នែកណាមួយនៃអារេដើម្បីជ្រើសរើសនៅពេលដែលយើងស្ថិតនៅធាតុពាក់កណ្តាលនៃអារេ? ដោយសារតែយើងមិនអាចអនុវត្តតាមក្បួនដោះស្រាយការស្វែងរកគោលពីរដើមពីព្រោះនេះជាអារេបង្វិលវិល។ ដូច្នេះមានការកែប្រែបន្តិចបន្តួចលើការស្វែងរកគោលពីរ។

ដូច្នេះជាធម្មតានៅក្នុងការស្វែងរកគោលពីរយើងពិនិត្យមើលថាតើធាតុបច្ចុប្បន្ន (ធាតុនៅពាក់កណ្តាលសន្ទស្សន៍) ដូចគ្នានឹងគោលដៅបន្ទាប់មកយើងត្រលប់មកវិញនូវសន្ទស្សន៍របស់វា។ ជំហាននេះនៅតែដដែល។ ក្រៅពីនេះប្រសិនបើពួកគេមិនដូចគ្នាយើងពិនិត្យមើលថាតើទ្រនិចបង្ហាញនៅខាងស្តាំ [នៃធាតុបច្ចុប្បន្នឬទៅខាងឆ្វេង។ ប្រសិនបើវាស្ថិតនៅខាងស្តាំបន្ទាប់មកយើងពិនិត្យមើលថាតើគោលដៅស្ថិតនៅក្នុងតំបន់រងដែលមិនវិលនោះទេប្រសិនបើវាធ្វើឱ្យទាន់សម័យខ្ពស់ជាងនេះយើងធ្វើបច្ចុប្បន្នភាពកម្រិតទាប។ ស្រដៀងគ្នានេះដែរប្រសិនបើចំណុច pivot ស្ថិតនៅខាងឆ្វេងជាថ្មីម្តងទៀតយើងពិនិត្យមើលថាតើគោលដៅស្ថិតនៅត្រង់ផ្លូវក្រោមដីដែលមិនបង្វិលយើងធ្វើបច្ចុប្បន្នភាពទាបបើមិនដូច្នេះទេយើងធ្វើបច្ចុប្បន្នភាពខ្ពស់។ ហើយនៅទីបញ្ចប់ប្រសិនបើយើងចេញពីរង្វិលជុំយើងប្រាកដថាគោលដៅមិនមាននៅក្នុងជួរដែលបានផ្តល់ឱ្យទេ។

លេខកូដប្រសើរសម្រាប់ស្វែងរកក្នុងដំណោះស្រាយវិលអារេ 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);
}
0

កូដចាវ៉ា

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

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (log N), ចាប់តាំងពីយើងបានប្រើការស្វែងរកគោលពីរដើម្បីរកធាតុគោលដៅ។ ភាពស្មុគស្មាញនៃពេលវេលាគឺលោការីត។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១), ដោយសារយើងបានរក្សាទុកតែធាតុមួយចំនួនថេរភាពចន្លោះទំនេរគឺថេរ។