භ්‍රමණය කළ වර්ග කළ අරා ලීට්කෝඩ් විසඳුමේ සොයන්න


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇෙබෝ අලිබබා ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් ByteDance සිස්කෝ ඊ බේ Expedia ෆේස්බුක් ගෝල්ඩ්මන් සැක්ස් ගූගල් ජේපී මෝගන් LinkedIn මයික්රොසොෆ්ට් නූටනික්ස් Nvidia ඔරකල් පේපෑල් Paytm Salesforce Samsung ජංගම දුරකථන සර්විස්නව් Tencent ටෙස්ලා ඇඞ්වයිසර් Twitch Uber වීසා VMware වෝල්මාර්ට් ලැබ් යාහූ Yandex සිලෝව් සුලිලි
අරා ද්විමය සෙවීම

වර්ග කළ අරාවක් සලකා බලන්න, නමුත් එක් දර්ශකයක් තෝරාගෙන එම අවස්ථාවේදී අරාව භ්‍රමණය විය. දැන්, අරාව භ්‍රමණය වූ පසු ඔබට නිශ්චිත ඉලක්ක මූලද්‍රව්‍යයක් සොයාගෙන එහි දර්ශකය ආපසු ලබා දිය යුතුය. මූලද්රව්යය නොමැති නම්, ආපසු -1. ගැටළුව සාමාන්‍යයෙන් හැඳින්වෙන්නේ භ්‍රමණය කළ වර්ග කළ අරා ලීට්කෝඩ් විසඳුමේ සෙවීම ලෙසිනි. එබැවින් ප්‍රශ්නයේදී, අප නොදන්නා නිශ්චිත දර්ශකයක වර්ග කර භ්‍රමණය වන පූර්ණ සංඛ්‍යා මූලද්‍රව්‍ය සමූහයක් අපට ලබා දී ඇත. අරාව සමඟ, අපට සොයා ගැනීමට අවශ්‍ය නිශ්චිත අංගයක් ද අපට ලබා දී ඇත.

භ්‍රමණය කළ වර්ග කළ අරා ලීට්කෝඩ් විසඳුමේ සොයන්න

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

පැහැදිලි කිරීම: සෙවිය යුතු මූලද්‍රව්‍යය 4 වන බැවින් මූලද්‍රව්‍යය දර්ශක 0 හි සොයාගත හැකි බැවින් අපි ඉලක්කයේ දර්ශකය නැවත ලබා දෙන්නෙමු.

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

පැහැදිලි කිරීම: අරාවෙහි මූලද්‍රව්‍යය නොපවතින බැවින්, අපි -1 නැවත ලබා දෙන්නෙමු.

භ්‍රමණය වූ වර්ග කළ අරාවෙහි සෙවීම සඳහා තිරිසන් බල ප්‍රවේශය

“භ්‍රමණය කළ වර්ග කළ අරාවෙහි සොයන්න” යන ගැටළුව අපෙන් ඉල්ලා සිටින්නේ දී ඇති භ්‍රමණය කළ වර්ග කළ අරාවෙහි ඉලක්කගත මූලද්‍රව්‍යයේ දර්ශකය සොයා ගැනීමට ය. භ්‍රමණය කළ වර්ග කළ අරාව යනු කුමක්දැයි අපි දැනටමත් සාකච්ඡා කර ඇත්තෙමු. එබැවින් කෙනෙකුට සිතිය හැකි සරලම ක්‍රමය වන්නේ රේඛීය සෙවීම උත්සාහ කිරීමයි. රේඛීය සෙවුමේදී, අපි ලබා දී ඇති දේ හරහා ගමන් කරමු අරාව වත්මන් මූලද්‍රව්‍යය අපගේ ඉලක්ක මූලද්‍රව්‍යය දැයි පරීක්ෂා කරන්න. වත්මන් මූලද්‍රව්‍යය ඉලක්කගත මූලද්‍රව්‍යය නම් අපි වත්මන් දර්ශකය නැවත ලබා දෙන්නෙමු. ප්රවේශය ඉතා සරල නමුත් එය අරාව වර්ග කර තනි දර්ශකයක භ්රමණය වන බව භාවිතා නොකරන බැවින්. මෙම ප්රවේශය රේඛීය කාල සංකීර්ණතාවයක් ඇත.

භ්‍රමණය කළ වර්ග කළ අරා ලීට්කෝඩ් විසඳුමේ සෙවීම සඳහා කේතය

සී ++ කේතය

#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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

මත), නරකම අවස්ථාවෙහිදී, අරාව අවසානයේ ඉලක්ක මූලද්‍රව්‍යය තිබිය හැක. මේ අනුව කාල සංකීර්ණතාව රේඛීය වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1), අපි එක් එක් මූලද්‍රව්‍යය පිළිබඳව නිශ්චිතවම කිසිදු තොරතුරක් නොදක්වන අතර නියත විචල්‍ය සංඛ්‍යාවක් භාවිතා කර ඇත. මේ අනුව අවකාශයේ සංකීර්ණතාව නියත ය.

භ්‍රමණය වූ වර්ග කළ අරා තුළ සෙවීම සඳහා ප්‍රශස්ත ප්‍රවේශය

කලින් සඳහන් කළ ප්‍රවේශය මඟින් අරාව භ්‍රමණය වූ වර්ග කළ අරාවක් යන කාරණය භාවිතා නොකළේය. ඉතින්, මෙම ප්රවේශය තුළ, කාලය සංකීර්ණතාව අඩු කිරීම සඳහා මෙම කරුණ භාවිතා කිරීමට අපි උත්සාහ කරමු. සලකා බලන්න, අපට වර්ග කළ අරාවක් තිබුනේ නම්, අපි සරලවම භාවිතා කරනු ඇත ද්විමය සෙවීම නමුත් මෙය ටිකක් උපක්‍රමශීලී නම්. මෙන්න අපි ද්විමය සෙවීම භාවිතා කිරීම අවශ්‍ය වේ. නමුත් අපි ද්විමය සෙවුම භාවිතා කරන්නේ නම්, අපි අරාවෙහි මැද අංගයට පැමිණි පසු තෝරා ගත යුත්තේ අරාවෙහි කුමන කොටසදැයි දැන ගන්නේ කෙසේද? මුල් ද්විමය සෙවුම් ඇල්ගොරිතම අපට සරලව අනුගමනය කළ නොහැකි නිසා මෙය භ්‍රමණය වූ වර්ග කළ අරාවකි. එබැවින් සාමාන්‍ය ද්විමය සෙවුමට වඩා සුළු වෙනස් කිරීමක් සිදු වේ.

එබැවින්, සාමාන්‍යයෙන් ද්විමය සෙවුමක දී, වත්මන් මූලද්‍රව්‍යය (මැද දර්ශකයේ මූලද්‍රව්‍යය) ඉලක්කයට සමාන දැයි අපි පරීක්ෂා කරමු, ඉන්පසු අපි එහි දර්ශකය ආපසු ලබා දෙමු. මෙම පියවර මෙහි එලෙසම පවතී. ඒ හැර, ඒවා සමාන නොවේ නම්, හැරීම [වත්මන් මූලද්‍රව්‍යයේ හෝ වමේ දකුණට පිහිටා තිබේදැයි අපි පරීක්ෂා කරමු. එය දකුණට පිහිටා තිබේ නම්, ඉලක්කය භ්‍රමණය නොවන උපආරයක තිබේදැයි අපි පරීක්ෂා කරමු, එය අප ඉහළට යාවත්කාලීන කරන්නේ නම් අපි අඩු යාවත්කාලීන කරන්නෙමු. ඒ හා සමානව, හැරීම වමට පිහිටා තිබේ නම්, ඉලක්කය භ්‍රමණය නොවන උපආරසයේ තිබේදැයි අපි නැවත පරීක්ෂා කරමු, අපි පහත් යාවත්කාලීන කරන්නෙමු, එසේ නොමැතිනම් අපි ඉහළ යාවත්කාලීන කරන්නෙමු. අවසානයේදී, අපි ලූපයෙන් පිටතට පැමිණියහොත්, ලබා දී ඇති අරාවෙහි ඉලක්කය නොපවතින බව අපට විශ්වාසයි.

භ්‍රමණය වූ වර්ග කළ අරා ලීට්කෝඩ් විසඳුමේ සෙවීම සඳහා ප්‍රශස්ත කේතය

සී ++ කේතය

#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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (ලොග් එන්), ඉලක්කගත මූලද්‍රව්‍යය සොයා ගැනීමට අපි ද්විමය සෙවුම් භාවිතා කර ඇති බැවින්. කාල සංකීර්ණතාව ල ar ු ගණකය වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1), අපි ගබඩා කර ඇත්තේ නියත මූලද්‍රව්‍ය කිහිපයක් පමණක් බැවින් අවකාශයේ සංකීර්ණතාව නියත ය.