လှည့်စီထားသော Array Leetcode Solution တွင်ရှာဖွေပါ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Adobe က အလီဘာဘာ အမေဇုံ Apple ဘလွန်းဘာ့ဂ် ByteDance Cisco သည် ကို eBay Expedia Facebook က Goldman Sachs Google JPMorgan LinkedIn တို့ Microsoft က Nutanix Nvidia က Oracle က PayPal က Paytm Salesforce Samsung ServiceNow Tencent တက်စလာ TripAdvisor Twitch Uber ဗီဇာ VMware က Walmart ဓာတ်ခွဲခန်းများ Yahoo က Yandex Zillow ကောင်မလေး
အခင်းအကျင်း Binary Search ကို

Sorted Array တစ်ခုကိုစဉ်းစားပါ။ ဒါပေမယ့် index တစ်ခုထဲကိုရွေးလိုက်ပြီးအဲဒီအချိန်မှာ array ကိုလှည့်လိုက်တယ်။ အခုဆိုရင် array ကိုလှည့်ပြီးတာနဲ့သင်ဟာ target element တစ်ခုကိုရှာပြီးသူ့ရဲ့ index ကိုပြန်သွားဖို့လိုအပ်တယ်။ အမှု၌၊ element သည်မရှိ၊ return -1 ။ ထိုပြgenerallyနာကိုယေဘူယျအားဖြင့်လှည့်စီထားသော Array Leetcode Solution တွင်ရှာဖွေခြင်းဟုရည်ညွှန်းသည်။ ဒါကြောင့်ဒီမေးခွန်းမှာကျွန်တော်တို့ကိုမသိသေးတဲ့အညွှန်းတစ်ခုမှာစီပြီးလှည့်ထားတဲ့ကိန်းဂဏန်းစုစုပေါင်းအချို့ပါ ၀ င်ပါတယ်။ Array နှင့်အတူကျွန်ုပ်တို့ရှာဖွေရန်လိုအပ်သောသီးခြား element တစ်ခုကိုလည်းပေးထားသည်။

လှည့်စီထားသော Array Leetcode Solution တွင်ရှာဖွေပါ

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

ရှင်းလင်းချက် - ရှာဖွေရမဲ့ element က ၄ ဖြစ်တာမို့ element ကို index 4 မှာတွေ့ပြီ၊ target ရဲ့ index ကို return ပြန်တယ်။

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

ရှင်းလင်းချက် - element က array ထဲမှာမရှိတဲ့အတွက် -1 ကိုပြန်ပို့တယ်။

လှည့်စီထားသော Array ကိုရှာဖွေရန် Brute Force ချဉ်းကပ်မှု

ပြ “နာ“ Search in Rotated Sorted Array” သည်လှည့်ထားသော sorted array ထဲမှ target element ၏အညွှန်းကိုရှာဖွေရန်ကျွန်ုပ်တို့အားတောင်းဆိုသည်။ ငါတို့သည်ပြီးသားလှည့်စီထားသောခင်းကျင်းသည်အဘယ်အရာကိုဆွေးနွေးကြပြီလော ထို့ကြောင့်စဉ်းစားနိုင်သောအရိုးရှင်းဆုံးနည်းလမ်းမှာ Linear Search ကိုကြိုးစားရန်ဖြစ်သည်။ Linear Search တွင်ကျွန်ုပ်တို့သည်ပေးထားသောအချက်အလက်များကိုသာဖြတ်သန်းသွားသည် အခင်းအကျင်း လက်ရှိဒြပ်စင်ကျွန်တော်တို့ရဲ့ပစ်မှတ်ဒြပ်စင်ဟုတ်မဟုတ်စစ်ဆေးပါ။ အကယ်၍ current element သည် target element ဖြစ်ပါကကျွန်ုပ်တို့သည်လက်ရှိ index ကို return ပြန်ပါမည်။ ချဉ်းကပ်နည်းသည်အလွန်ရိုးရှင်းသည်။ သို့သော်၎င်းကိုအညွှန်းတစ်ခုတည်းဖြင့်စီပြီးလှည့်သည်ဟူသောအချက်ကိုမသုံးသောကြောင့်။ ဤသည်ချဉ်းကပ်မှု linear အချိန်ရှုပ်ထွေးရှိပါတယ်။

လှည့် Sorted Array 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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N)၊ ဘာလို့လဲဆိုတော့အဆိုးဆုံးအခြေအနေမှာ target element ရဲ့ array မှာရှိနေနိုင်လို့ပါ။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုမှာ linear ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (၁)ကျွန်ုပ်တို့သည် element တစ်ခုစီနှင့်ပတ်သက်သောမည်သည့်သတင်းအချက်အလက်ကိုမဆိုအထူးသဖြင့် variable များ၏စဉ်ဆက်မပြတ်အရေအတွက်ကိုအသုံးပြုသောကြောင့်ဖြစ်သည်။ ထို့ကြောင့်အာကာသရှုပ်ထွေးစဉ်ဆက်မပြတ်ဖြစ်ပါတယ်။

Rotated Sorted Array တွင်ရှာဖွေရန်အတွက်အကောင်းဆုံးနည်းလမ်း

အစောပိုင်းကဖော်ပြခဲ့သည့်ချဉ်းကပ်နည်းသည် array ကိုလှည့်ထားသော sorted array ဟူသောအချက်ကိုမသုံးခဲ့ပါ။ ဒါကြောင့်ဒီချဉ်းကပ်မှုမှာအချိန်ရှုပ်ထွေးမှုကိုလျှော့ချဖို့ဒီအချက်ကိုအသုံးပြုဖို့ကြိုးစားတယ်။ စဉ်းစားကြည့်ပါ၊ အကယ်၍ ကျွန်တော်တို့မှာ sorted array ရှိရင်၊ binary ရှာဖွေရေး ဒါပေမယ့်အမှု၌ဤနည်းနည်းလှည်သည်။ ဒီမှာ binary search ကိုအသုံးပြုဖို့လိုတယ်။ သို့သော်ကျွန်ုပ်တို့သည် binary search ကိုသုံးပါက array ၏အလယ်ဗဟိုတွင်ရှိသောအခါမည်သည့်အပိုင်းကိုရွေးရမည်ကိုကျွန်ုပ်တို့မည်သို့သိရမည်နည်း။ အဘယ်ကြောင့်ဆိုသော်ကျွန်ုပ်တို့သည်မူလ binary search algorithm ကို လိုက်၍ မရနိုင်ပါ၊ ဒါကြောင့်ပုံမှန် binary search အပေါ်အနည်းငယ်ပြုပြင်မှုတစ်ခုရှိသည်။

ထို့ကြောင့်ပုံမှန်အားဖြင့် binary search တစ်ခုတွင်ကျွန်ုပ်တို့သည်လက်ရှိ element (element at mid index) သည် target နှင့်တူညီမှုရှိမရှိစစ်ဆေးသည်၊ ၄ င်းသည်၎င်း၏ index ကို return ပြန်သည်။ ဒီအဆင့်ကဒီမှာအတူတူပဲ။ ထို့အပြင်၎င်းတို့သည်မတူညီပါကမဏ္pိုင်သည်ညာဘက် [လက်ရှိဒြပ်စင်၏ (သို့) ဘယ်ဘက်တွင်တည်ရှိသည်ကိုကျွန်ုပ်တို့စစ်ဆေးသည်။ အကယ်၍ ၎င်းသည်ညာဘက်တွင်ရှိလျှင်၊ ပစ်မှတ်သည်လှည့်မထားသောလှည့်ဖျားတွင်တည်ရှိသည်ကိုကျွန်ုပ်တို့စစ်ဆေးသည်။ အမြင့်ကိုကျွန်ုပ်တို့အသစ်ပြောင်းခြင်းကိုကျွန်ုပ်တို့ထပ်မံစစ်ဆေးသည်။ အလားတူစွာမဏ္ivိုင်သည်ဘယ်ဘက်တွင်တည်ရှိသည်ဆိုလျှင်၊ ပစ်မှတ်သည်လှည့်မထားသောလှိုင်းအလျားတွင်တည်ရှိသည်ကိုကျွန်ုပ်တို့ထပ်မံစစ်ဆေးသည်။ အနိမ့်ကိုမွမ်းမံသည်၊ နောက်ဆုံးအနေဖြင့်ကျွန်ုပ်တို့သည် loop မှထွက်လျှင် target သည်ထို array တွင်မရှိကြောင်းသေချာပါသည်။

Rotated Sorted Array Leetcode Solution အတွက်ရှာဖွေရန်အတွက်အကောင်းဆုံးကုဒ်

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (မှတ်တမ်း N)၊ ကျနော်တို့ပစ်မှတ်ဒြပ်စင်ကိုရှာဖွေ binary ရှာဖွေရေးကိုသုံးပါကတည်းက။ အချိန်ရှုပ်ထွေး logarithmic ဖြစ်ပါတယ်။

အာကာသရှုပ်ထွေးမှု

အို (၁)၊ ကျွန်ုပ်တို့သည်စဉ်ဆက်မပြတ်သောဒြပ်စင်အချို့ကိုသာသိမ်းဆည်းထားသောကြောင့်၊