ຄົ້ນຫາ Element ໃນ SRL ພືດຫມູນວຽນແບບຈັດລຽງລໍາດັບ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg ByteDance eBay Expedia ເຟສບຸກ ກູໂກ Microsoft Nvidia Oracle PayPal Paytm VMware Walmart Labs Zillow
Array ການຄົ້ນຫາຖານສອງ

ໃນການຊອກຫາໃນການຈັດລຽງ ໝູນ ວຽນ array ບັນຫາທີ່ພວກເຮົາໄດ້ຈັດໃຫ້ມີການຈັດລຽງແລະ ໝູນ ວຽນແລະອົງປະກອບໃດ ໜຶ່ງ, ໃຫ້ກວດເບິ່ງວ່າອົງປະກອບທີ່ມອບໃຫ້ນັ້ນມີຢູ່ໃນແຖວຫຼືບໍ່.

ຕົວຢ່າງ

ການປ້ອນຂໍ້ມູນ
nums [] = {2, 5, 6, 0, 0, 1, 2}
ເປົ້າ ໝາຍ = 0
ຜົນຜະລິດ
ທີ່ແທ້ຈິງ

ຄົ້ນຫາ Element ໃນ SRL ພືດຫມູນວຽນແບບຈັດລຽງລໍາດັບ

ການປ້ອນຂໍ້ມູນ
nums [] = {2, 5, 6, 0, 0, 1, 2}
ເປົ້າ ໝາຍ = 3
ຜົນຜະລິດ
ທີ່ບໍ່ຖືກຕ້ອງ

ວິທີການທີ່ບໍ່ມີປະໂຫຍດ ສຳ ລັບການຄົ້ນຫາອົງປະກອບໃນ Arrrated Rotated Array

ເສັ້ນລຽບຕາມເສັ້ນໃນແຖວແລະຄົ້ນຫາມູນຄ່າເປົ້າ ໝາຍ.

  1. ດໍາເນີນການ loop ສໍາລັບ i = 0 ເຖິງ n (ບໍ່ລວມ), ບ່ອນທີ່ n ແມ່ນຈໍານວນຂອງອົງປະກອບໃນແຖວ.
  2. ໃນທຸກໆເວລາທີ່ເກີດຂື້ນ ໃໝ່, ໃຫ້ກວດເບິ່ງວ່າຕົວເລກ [i] ເທົ່າກັບຄ່າເປົ້າ ໝາຍ ຫຼືບໍ່. ຖ້າມັນເທົ່າທຽມກັນ, ກັບຄືນມາເປັນຄວາມຈິງ, ສິ່ງອື່ນຈະສືບຕໍ່ ສຳ ລັບອົງປະກອບຕໍ່ໄປ.
  3. ຖ້າບໍ່ມີອົງປະກອບໃດທຽບເທົ່າກັບມູນຄ່າເປົ້າ ໝາຍ, ໃຫ້ສົ່ງຄືນທີ່ບໍ່ຖືກຕ້ອງ.

ລະຫັດ JAVA

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

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການຄົ້ນຫາອົງປະກອບໃນການຈັດລຽງ Array

ຄວາມສັບສົນເວລາ = O (n)
ຄວາມສັບສົນໃນອະວະກາດ = O (1) 
ບ່ອນທີ່ n ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບທີ່ຢູ່ໃນຂບວນ.

ວິທີການທີ່ດີທີ່ສຸດ ສຳ ລັບການຄົ້ນຫາອົງປະກອບໃນການຈັດລຽງ Array

ຂບວນການອາດຈະບັນຈຸຊ້ ຳ ຊ້ອນກັນ, ສະນັ້ນແນວຄວາມຄິດຂອງການແບ່ງອາເລເປັນສອງຂບວນຈັດລຽງ ລຳ ດັບຈະບໍ່ເຮັດວຽກ.

ໃຫ້ດັດສະນີເລີ່ມຕົ້ນຂອງແຖວເປັນ l ແລະດັດຊະນີສິ້ນສຸດແມ່ນ h,

  1. ຊອກຫາກາງ, ເປັນກາງ = (l + h) / 2.
  2. ຖ້າມາຮອດ [ກາງ] ເທົ່າກັບມູນຄ່າເປົ້າ ໝາຍ, ໃຫ້ກັບຄືນມາຖືກຕ້ອງ.
  3. ຖ້າ arr [l] ເທົ່າກັບ arr [h] ແມ່ນເທົ່າກັບ arr [ກາງ], ຫຼັງຈາກນັ້ນ increment l ແລະ h h.
  4. ອີກອັນ ໜຶ່ງ ຖ້າ arr [l] ໜ້ອຍ ກວ່າຫຼືເທົ່າກັບ arr [ກາງ], ຫຼັງຈາກນັ້ນອີກເຄິ່ງ ໜຶ່ງ ແມ່ນຖືກຈັດຮຽງ, ຖ້າເປົ້າ ໝາຍ ແມ່ນຢູ່ໃນລະດັບຂອງເຄິ່ງຊ້າຍທີ່ຈັດລຽງ, ໃຫ້ຄົ້ນຫາໃນເຄິ່ງ ໜຶ່ງ ຊ້າຍຊອກຫາໃນເຄິ່ງຂວາ.
  5. ຖ້າເງື່ອນໄຂຂ້າງເທິງບໍ່ແມ່ນຄວາມຈິງ, ເຄິ່ງຂວາມືຕັ້ງແຕ່ກາງຮອດ h, ຖືກຈັດຮຽງ, ຖ້າເປົ້າ ໝາຍ ແມ່ນຢູ່ໃນລະດັບຂອງເຄິ່ງ ໜຶ່ງ ທີ່ຖືກຈັດຮຽງດ້ານຂວາ, ໃຫ້ຊອກຫາໃນເຄິ່ງ ໜຶ່ງ ທີ່ຖືກຕ້ອງໃນການຊອກຫາໃນເຄິ່ງຊ້າຍ

ລະຫັດ JAVA

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

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການຄົ້ນຫາອົງປະກອບໃນການຈັດລຽງ Array

ຄວາມສັບສົນເວລາ = O (log n)
ຄວາມສັບສົນໃນອະວະກາດ = O (1) 
ບ່ອນທີ່ n ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບທີ່ຢູ່ໃນຂບວນ.

ເອກະສານ