ຄົ້ນຫາໃນ Rotate Sorted Array Leetcode Solution


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Adobe ອາລີບາບາ Amazon ຈາກຫນາກແອບເປີ Bloomberg ByteDance Cisco eBay Expedia ເຟສບຸກ Goldman Sachs ກູໂກ JPMorgan LinkedIn Microsoft Nutanix Nvidia Oracle PayPal Paytm Salesforce Samsung ServiceNow Tencent Tesla TripAdvisor Twitch Uber ສະແດງໃຫ້ເຫັນ VMware Walmart Labs Yahoo Yandex Zillow ກະລຸນາ
Array ການຄົ້ນຫາຖານສອງ

ພິຈາລະນາຕາຕະລາງທີ່ຈັດລຽງແຕ່ວ່າດັດຊະນີ ໜຶ່ງ ຖືກເກັບແລະແຖວກໍ່ຖືກ ໝູນ ວຽນຢູ່ຈຸດນັ້ນ. ດຽວນີ້, ເມື່ອອາການຖືກ ໝູນ ວຽນແລ້ວທ່ານ ຈຳ ເປັນຕ້ອງຊອກຫາອົງປະກອບເປົ້າ ໝາຍ ສະເພາະແລະສົ່ງຄືນດັດຊະນີຂອງມັນ. ໃນກໍລະນີ, ອົງປະກອບບໍ່ຢູ່, ໃຫ້ກັບຄືນ -1. ບັນຫາໂດຍທົ່ວໄປຈະຖືກເອີ້ນວ່າຄົ້ນຫາໃນ Rotated Sorted Array Leetcode Solution. ດັ່ງນັ້ນ, ໃນ ຄຳ ຖາມ, ພວກເຮົາໄດ້ຖືກຈັດຫາດ້ວຍສ່ວນປະກອບຂອງ ຈຳ ນວນ ໜຶ່ງ ທີ່ຖືກຈັດຮຽງແລະ ໝູນ ວຽນຢູ່ທີ່ດັດສະນີສະເພາະໃດ ໜຶ່ງ ທີ່ພວກເຮົາບໍ່ຮູ້ຈັກ. ຄຽງຄູ່ກັບອາເລ, ພວກເຮົາຍັງໄດ້ຮັບອົງປະກອບສະເພາະທີ່ພວກເຮົາຕ້ອງການຊອກຫາ.

ຄົ້ນຫາໃນ Rotate Sorted Array Leetcode Solution

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.

ແນວທາງຂອງ Brute Force ສຳ ລັບການຄົ້ນຫາໃນ Rotated Sorted Array

ບັນຫາ "ຄົ້ນຫາໃນ Rotate Sorted Array" ຂໍໃຫ້ພວກເຮົາຊອກຫາດັດສະນີຂອງອົງປະກອບເປົ້າ ໝາຍ ໃນແຖວທີ່ຈັດລຽງ ໝູນ ວຽນ. ແລະພວກເຮົາໄດ້ປຶກສາຫາລືກັນແລ້ວວ່າຂບວນການ ໝູນ ວຽນແບບໃດ? ດັ່ງນັ້ນ, ວິທີການທີ່ງ່າຍທີ່ສຸດທີ່ຄົນເຮົາສາມາດຄິດໄດ້ຄືການລອງ Linear Search. ໃນການຊອກຫາເສັ້ນ, ພວກເຮົາພຽງແຕ່ຜ່ານສິ່ງທີ່ກ່າວມາ array ແລະກວດເບິ່ງວ່າອົງປະກອບປັດຈຸບັນແມ່ນອົງປະກອບເປົ້າ ໝາຍ ຂອງພວກເຮົາ. ຖ້າອົງປະກອບປັດຈຸບັນແມ່ນອົງປະກອບເປົ້າ ໝາຍ ພວກເຮົາສົ່ງດັດສະນີປະຈຸບັນໄປອີກ, ພວກເຮົາກັບຄືນ -1. ວິທີການແມ່ນງ່າຍດາຍຫຼາຍແຕ່ຍ້ອນວ່າມັນບໍ່ໄດ້ໃຊ້ຄວາມຈິງທີ່ວ່າອາເລຖືກຈັດລຽງແລະ ໝູນ ວຽນຢູ່ທີ່ດັດສະນີດຽວ. ວິທີການນີ້ມີຄວາມສັບສົນເວລາເປັນເສັ້ນ.

ລະຫັດ ສຳ ລັບການຊອກຫາໃນການແກ້ໄຂແບບ ໝູນ ວຽນແບບເລີແກເລີ 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

Java Code

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), ເນື່ອງຈາກວ່າໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດ, ສ່ວນປະກອບເປົ້າ ໝາຍ ອາດຈະມີຢູ່ໃນຕອນທ້າຍຂອງຂບວນ. ດັ່ງນັ້ນຄວາມສັບສົນທີ່ໃຊ້ເວລາແມ່ນເປັນເສັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

O (1), ເນື່ອງຈາກວ່າພວກເຮົາບໍ່ມີຂໍ້ມູນໃດໆກ່ຽວຂ້ອງກັບແຕ່ລະອົງປະກອບໂດຍສະເພາະແລະໄດ້ ນຳ ໃຊ້ຕົວແປ ຈຳ ນວນຄົງທີ່. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ແມ່ນຄົງທີ່.

ວິທີການທີ່ດີທີ່ສຸດ ສຳ ລັບການຄົ້ນຫາໃນ Rotated Sorted Array

ວິທີການທີ່ກ່າວມາກ່ອນ ໜ້າ ນີ້ບໍ່ໄດ້ໃຊ້ຄວາມຈິງທີ່ວ່າຂບວນແມ່ນການຈັດລຽງແບບ ໝູນ ວຽນ. ສະນັ້ນ, ໃນວິທີການນີ້, ພວກເຮົາພະຍາຍາມ ນຳ ໃຊ້ຄວາມຈິງນີ້ເພື່ອຫຼຸດຜ່ອນຄວາມສັບສົນເວລາ. ພິຈາລະນາ, ຖ້າພວກເຮົາມີອາເລທີ່ຈັດລຽງ ລຳ ດັບ, ພວກເຮົາຈະໄດ້ ນຳ ໃຊ້ແບບ ທຳ ມະດາ ຄົ້ນຫາຖານສອງ ແຕ່ໃນກໍລະນີນີ້ມັນເປັນເລື່ອງຍາກ. ນີ້ພວກເຮົາຍັງ ຈຳ ເປັນຕ້ອງໃຊ້ການຄົ້ນຫາຖານສອງ. ແຕ່ຖ້າພວກເຮົາໃຊ້ການຄົ້ນຫາຖານສອງ, ພວກເຮົາຈະຮູ້ໄດ້ແນວໃດວ່າສ່ວນໃດຂອງອາເລທີ່ຈະເລືອກເອົາເມື່ອພວກເຮົາຢູ່ໃນສ່ວນກາງຂອງອາເລ? ເນື່ອງຈາກວ່າພວກເຮົາບໍ່ສາມາດປະຕິບັດຕາມຫຼັກການຄົ້ນຫາຖານສອງແບບເດີມເພາະວ່ານີ້ແມ່ນຂບວນການ ໝູນ ວຽນແບບ ໝູນ ວຽນ. ດັ່ງນັ້ນ, ມີການດັດແປງເລັກນ້ອຍກວ່າການຄົ້ນຫາຖານສອງ ທຳ ມະດາ.

ດັ່ງນັ້ນ, ໂດຍປົກກະຕິໃນການຄົ້ນຫາຖານສອງ, ພວກເຮົາກວດເບິ່ງວ່າປັດຈຸບັນ (ອົງປະກອບທີ່ຢູ່ກາງດັດສະນີ) ແມ່ນຄືກັນກັບເປົ້າ ໝາຍ, ຫຼັງຈາກນັ້ນພວກເຮົາສົ່ງດັດສະນີຂອງມັນຄືນ. ຂັ້ນຕອນນີ້ຍັງຄົງຢູ່ຄືເກົ່າ. ນອກ ເໜືອ ຈາກນັ້ນ, ຖ້າວ່າມັນບໍ່ຄືກັນ, ພວກເຮົາກວດເບິ່ງວ່າຕົວຢ່າງທີ່ຢູ່ເບື້ອງຂວາ [ຂອງອົງປະກອບປັດຈຸບັນຫລືເບື້ອງຊ້າຍ. ຖ້າມັນຕັ້ງຢູ່ເບື້ອງຂວາ, ຫຼັງຈາກນັ້ນພວກເຮົາກວດເບິ່ງວ່າເປົ້າ ໝາຍ ແມ່ນນອນຢູ່ໃນເສັ້ນທາງໃຕ້ດິນທີ່ບໍ່ ໝູນ ວຽນ, ຖ້າມັນປັບປຸງໃຫ້ສູງຂື້ນອີກພວກເຮົາປັບປຸງລະດັບຕໍ່າ. ເຊັ່ນດຽວກັນ, ຖ້າຕົວຊີ້ວັດຢູ່ທາງເບື້ອງຊ້າຍ, ອີກເທື່ອ ໜຶ່ງ ພວກເຮົາກວດເບິ່ງວ່າເປົ້າ ໝາຍ ນອນຢູ່ໃນເສັ້ນທາງໃຕ້ດິນທີ່ບໍ່ ໝູນ ວຽນ, ພວກເຮົາປັບປຸງລະດັບຕໍ່າ, ຖ້າບໍ່ດັ່ງນັ້ນພວກເຮົາປັບປຸງຈຸດສູງ. ແລະໃນທີ່ສຸດ, ຖ້າພວກເຮົາອອກມາຈາກວົງຈອນ, ພວກເຮົາແນ່ໃຈວ່າເປົ້າ ໝາຍ ບໍ່ໄດ້ຢູ່ໃນອາເລທີ່ລະບຸ.

ລະຫັດທີ່ດີທີ່ສຸດ ສຳ ລັບການຄົ້ນຫາໃນ Rotate 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

ລະຫັດ 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));
    }
}
0

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (log N), ນັບຕັ້ງແຕ່ພວກເຮົາໄດ້ໃຊ້ການຄົ້ນຫາຖານສອງເພື່ອຊອກຫາອົງປະກອບເປົ້າ ໝາຍ. ຄວາມສັບສົນຂອງເວລາແມ່ນ logarithmic.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (1), ເນື່ອງຈາກວ່າພວກເຮົາເກັບພຽງແຕ່ບາງສ່ວນຂອງສ່ວນປະກອບທີ່ ຈຳ ກັດເທົ່ານັ້ນ, ຄວາມສັບສົນຂອງພື້ນທີ່ກໍ່ຄົງທີ່.