Sorted Rotated Array တွင် Element တစ်ခုကိုရှာပါ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Adobe က အမေဇုံ Apple ဘလွန်းဘာ့ဂ် ByteDance ကို eBay Expedia Facebook က Google Microsoft က Nvidia က Oracle က PayPal က Paytm VMware က Walmart ဓာတ်ခွဲခန်းများ Zillow
အခင်းအကျင်း Binary Search ကို

ရှာဖွေရေးအတွက်လှည့်စီလှည့် အခင်းအကျင်း ကျွန်တော် sorted နှင့်လှည့်ခင်းကျင်းခြင်းနှင့်ဒြပ်စင်ပေးသောပြproblemနာ, ပေးထားသောဒြပ်စင်ခင်းကျင်းထဲမှာပစ္စုပ္ပန်သို့မဟုတ်မရှိမရှိစစ်ဆေးပါ။

ဥပမာ

input
nums [] = {2, 5, 6, 0, 0, 1, 2}
ပစ်မှတ် = 0
output
စစ်မှန်တဲ့

Sorted Rotated Array တွင် Element တစ်ခုကိုရှာပါ

input
nums [] = {2, 5, 6, 0, 0, 1, 2}
ပစ်မှတ် = 3
output
မမှန်သော

Sorted Rotated Array တွင်ရှာဖွေရန် Element တစ်ခုကို Naive Approach

စစ်ခင်းကျင်းမှုအတွင်း Linear ဖြတ်သန်းပြီးပစ်မှတ်တန်ဖိုးကိုရှာဖွေပါ။

  1. i = 0 to loop (မပါ ၀ င်ပါ) အတွက် loop တစ်ခုကို run ပါ။ n သည် array အတွင်းရှိ element များ၏နံပါတ်ဖြစ်သည်။
  2. ကြားဖြတ်တိုင်းတွင် nums [i] သည်သတ်မှတ်တန်ဖိုးနှင့်ညီသည်မဟုတ်ကိုစစ်ဆေးပါ။ အကယ်၍ ညီမျှလျှင် return ပြန်လုပ်ပါ၊ နောက် element တစ်ခုအတွက်ဆက်လက်လုပ်ဆောင်ပါ။
  3. ပစ်မှတ်တန်ဖိုးနှင့်ညီမျှသောဒြပ်စင်မရှိလျှင် false ပြန်ပို့ပါ။

Java Code ကို

public class SearchInRotatedAndSortedArray {
    private static boolean searchTarget(int[] nums, int target) {
        int n = nums.length;
        // Traverse the given array and search for the target value
        for (int i = 0; i < n; i++) {
            if (nums[i] == target) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{2, 5, 6, 0, 0, 1, 2};
        int target = 0;

        System.out.println(searchTarget(nums, target));

        // Example 2
        target = 3;

        System.out.println(searchTarget(nums, target));
    }
}
true
false

C ++ ကုဒ်

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

bool searchTarget(int *nums, int target, int n) {
    // Traverse the given array and search for the target value
    for (int i = 0; i < n; i++) {
        if (nums[i] == target)
            return true;
    }
    return false;
}

int main() {
    // Example 1
    int nums[] = {2, 5, 6, 0, 0, 1, 2};
    int target = 0;
    int n = sizeof(nums) / sizeof(nums[0]);
    
    if (searchTarget(nums, target, n)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    target = 3;
    
    if (searchTarget(nums, target, n)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
true
false

Searched အတွက်ရှုပ်ထွေးမှုအားခွဲခြမ်းစိတ်ဖြာခြင်း Sorted Rotated Array တွင် Element တစ်ခု

အချိန်ရှုပ်ထွေး = အို (ဎ)
အာကာသရှုပ်ထွေး = အို (၁) 
အဘယ်မှာ n n ခင်းကျင်းအတွက် element များ၏အရေအတွက်သည်။

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

Array တွင်ထပ်တူများပါဝင်နိုင်သဖြင့် Array ကိုနှစ်မျိုးခွဲခြားရန်စိတ်ကူးမကောင်းပေ။

array ရဲ့ start index က l ဖြစ်ဖြစ်၊ end index က h ဖြစ်ရမယ်။

  1. နှစ်လယ်ပိုင်း = (ဌ + ဇ) / 2 အဖြစ်နှစ်လယ်ပိုင်းကိုရှာပါ။
  2. arr [mid] သည်ပစ်မှတ်တန်ဖိုးနှင့်ညီပါက true သို့ပြန်သွားပါ။
  3. arr [l] သည် arr [h] နှင့်ထပ်တူပါက arr [mid] နှင့်ညီလျှင် l နှင့် decrement h တိုးပါ။
  4. အကယ်၍ arr [l] သည် arr [mid] ထက်ငယ်သို့မဟုတ်ညီမျှလျှင်ကျန်ရှိသောတစ်ဝက်ကိုခွဲခြားသည်။ ပစ်မှတ်သည်ခွဲခြားထားသည့်ဘယ် ၀ က်၏အကွာအဝေးတွင်တည်ရှိပါက၊ ဘယ်ဘက်တစ်ဝက်တွင်အခြားရှာရန်ကိုညာဘက်တစ်ဝက်တွင်ရှာဖွေပါ။
  5. အထက်ပါအခြေအနေသည်မမှန်ပါက၊ ညာဘက်တစ်ဝက်မှအလယ်သို့ဇကိုစီသည်။ ပစ်မှတ်သည်ခွဲထားသည့်ညာဘက်တစ်ဝက်တွင်ရှိလျှင်ညာဘက်တစ်ဝက်တွင်အခြားဘယ်ဘက်တွင်ရှာဖွေပါ။

Java Code ကို

public class SearchInRotatedAndSortedArray {
    private static boolean searchTarget(int[] nums, int target, int l, int h) {
        // Index out of bound, element does not exist
        if (l > h)
            return false;
        // Find the middle element
        int mid = (l + h) / 2;
        // If this is the target element, return true
        if (nums[mid] == target) {
            return true;
        }
        // If nums[l] = nums[h] = nums[mid], increment l and decrement h
        if (nums[l] == nums[mid] && nums[h] == nums[mid]) {
            return searchTarget(nums, target, l + 1, h - 1);
        }
        
        // If nums[l] <= nums[mid], left half is sorted
        if (nums[l] <= nums[mid]) {
            // If the target lies in the first half, search in first half
            if (target >= nums[l] && target <= nums[mid]) {
                return searchTarget(nums, target, l, mid - 1);
            }
            // Else search in second half
            return searchTarget(nums, target, mid + 1, h);
        }
        
        // If first half is not sorted, then second half is sorted
        // If the target is present in the second half, search in second half
        if (target >= nums[mid] && target <= nums[h]) {
            return searchTarget(nums, target, mid + 1, h);
        }
        // Else search in the first half
        return searchTarget(nums, target, l, mid - 1);
    }
    
    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{2, 5, 6, 0, 0, 1, 2};
        int target = 0;
        
        System.out.println(searchTarget(nums, target, 0, nums.length - 1));
        
        // Example 2
        target = 3;

        System.out.println(searchTarget(nums, target, 0, nums.length - 1));
    }
}
true
false

C ++ ကုဒ်

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

bool searchTarget(int *nums, int target, int l, int h) {
    // Index out of bound, element does not exist
    if (l > h)
        return false;
    // Find the middle element
    int mid = (l + h) / 2;
    // If this is the target element, return true
    if (nums[mid] == target)
        return true;
    // If nums[l] = nums[h] = nums[mid], increment l and decrement h
    if (nums[l] == nums[mid] && nums[h] == nums[mid]) {
        return searchTarget(nums, target, l + 1, h - 1);
    }
    
    // If nums[l] <= nums[mid], left half is sorted
    if (nums[l] <= nums[mid]) {
        // If the target lies in the first half, search in first half
        if (target >= nums[l] && target <= nums[mid]) {
            return searchTarget(nums, target, l, mid - 1);
        }
        // Else search in second half
        return searchTarget(nums, target, mid + 1, h);
    }

    // If first half is not sorted, then second half is sorted
    // If the target is present in the second half, search in second half
    if (target >= nums[mid] && target <= nums[h]) {
        return searchTarget(nums, target, mid + 1, h);
    }
    // Else search in the first half
    return searchTarget(nums, target, l, mid - 1);
}

int main() {
    // Example 1
    int nums[] = {2, 5, 6, 0, 0, 1, 2};
    int target = 0;
    int n = sizeof(nums) / sizeof(nums[0]);
    
    if (searchTarget(nums, target, 0, n - 1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    target = 3;
    
    if (searchTarget(nums, target, 0, n - 1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
true
false

Searched အတွက်ရှုပ်ထွေးမှုအားခွဲခြမ်းစိတ်ဖြာခြင်း Sorted Rotated Array တွင် Element တစ်ခု

အချိန်ရှုပ်ထွေး = အို (log n)
အာကာသရှုပ်ထွေး = အို (၁) 
အဘယ်မှာ n n ခင်းကျင်းအတွက် element များ၏အရေအတွက်သည်။

ကိုးကား