ຊອກຫາວິທີແກ້ໄຂ ຕຳ ແໜ່ງ ທີ່ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg ກູໂກ Microsoft
Array ການຄົ້ນຫາຖານສອງ

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ຮັບການຈັດຮຽງ array ແລະຕົວເລກເປົ້າ ໝາຍ. ພວກເຮົາຕ້ອງຊອກຫາ ຕຳ ແໜ່ງ Search Insert ຂອງມັນ.

  1. ຖ້າມູນຄ່າເປົ້າ ໝາຍ ມີຢູ່ໃນຂບວນ, ໃຫ້ດັດສະນີຂອງມັນຄືນ.
  2. ສົ່ງຄືນດັດຊະນີທີ່ເປົ້າ ໝາຍ ຄວນຖືກໃສ່ເພື່ອທີ່ຈະຮັກສາການຈັດລຽງ ລຳ ດັບ (ໃນລັກສະນະທີ່ບໍ່ມີການຫຼຸດລົງ).

ຍົກຕົວຢ່າງ

1 2 3 4 5 
Target = 3
2
1 3 5 7 9
Target = 8
4

ຄໍາອະທິບາຍ

ຄົ້ນຫາ ຕຳ ແໜ່ງ ວິທີແກ້ໄຂ Leetcode

ວິທີການ (ຄົ້ນຫາເສັ້ນຊື່)

ພວກເຮົາສາມາດແລ່ນ loop ເພື່ອຊອກຫາດັດສະນີ ທຳ ອິດທີ່ມີມູນຄ່າເກີນຫລືເທົ່າກັບມູນຄ່າເປົ້າ ໝາຍ. ຫຼັກຖານສະແດງ:

  • ຖ້າມູນຄ່າເທົ່າກັບ, ຫຼັງຈາກນັ້ນດັດຊະນີນີ້ແມ່ນດັດສະນີທີ່ຕ້ອງການ.
  • ເປົ້າ ໝາຍ ອາດຈະຖືກໃສ່ຢູ່ໃນ ຕຳ ແໜ່ງ ນີ້, ຖ້າບໍ່ດັ່ງນັ້ນ.

ລະບົບວິເຄາະ

  1. ດໍາເນີນການ loop ຈາກດັດຊະນີທໍາອິດໄປໃນຕອນທ້າຍຂອງ array ໄດ້
  2. If ຈັດລຽງ [i] ເກີນຫຼືເທົ່າກັບມູນຄ່າເປົ້າ ໝາຍ, ຫຼັງຈາກນັ້ນກັບຄືນ i
  3. ການກັບຄືນມາ n, ດັ່ງທີ່ພວກເຮົາພົບວ່າບໍ່ມີດັດສະນີດັ່ງກ່າວ array [ດັດສະນີ]> = ເປົ້າ ໝາຍ, ດັ່ງນັ້ນ ເປົ້າ​ຫມາຍ ຄວນໃສ່ໃນທີ່ສຸດ
  4. ພິມຜົນໄດ້ຮັບ

ການຈັດຕັ້ງປະຕິບັດລະບົບ algorithm ເພື່ອຊອກຫາ Search Insert Position of Target

ໂຄງການ C ++

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

int searchInsert(vector<int>& a, int target)
{
    int n = a.size();
    for(int i = 0 ; i < n ; i++)
    {
        if(a[i] >= target)
            return i;
    }
    return n;
}


int main()
{
    vector <int> a = {1 , 3 , 5 , 7 , 9};
    int target = 8;
    cout << searchInsert(a , target) << '\n';
}

Java Program

class search_insert_position
{
    static int searchInsert(int[] a , int target)
    {
        int n = a.length;
        for(int i = 0 ; i < n ; i++)
        {
            if(a[i] >= target)
                return i;
        }
        return n;
    }

    public static void main(String args[])
    {
        int a[] = {1 , 3 , 5 , 7 , 9} , target = 8;
        System.out.println(searchInsert(a , target));
    }
}
4

ການວິເຄາະຄວາມສັບສົນຂອງການຊອກຫາການຊອກຫາການຊອກຫາ ຕຳ ແໜ່ງ ເປົ້າ ໝາຍ

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

ໂອ (N), ບ່ອນທີ່ N = ຂະ ໜາດ ຂອງຂບວນ. ໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດ, ພວກເຮົາຕ້ອງການອຸປະຖໍາ ເປົ້າ​ຫມາຍ ໃນຕອນທ້າຍຂອງຂບວນການ.

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

O (1). ພວກເຮົາໃຊ້ພື້ນທີ່ຄົງທີ່ ສຳ ລັບຕົວແປຕ່າງໆ.

ວິທີການ (ການຄົ້ນຫາຖານສອງ)

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

ລະບົບວິເຄາະ

  1. ສ້າງເປັນ binarySearch () ຫນ້າທີ່ທີ່ສົ່ງຄືນດັດສະນີທີ່ຕ້ອງການ
  2. ເລີ່ມຕົ້ນ ans = 0, ເຊິ່ງຈະເກັບຮັກສາດັດສະນີທີ່ຕ້ອງການ
  3. ກຳ ນົດຂອບເຂດເບື້ອງຊ້າຍແລະຂວາຄື 0 ແລະ N - 1 ຕາມ ລຳ ດັບ, N = ຂະ ໜາດ ຂອງຂບວນ
  4. ຈົນກ່ວາ ຊ້າຍ <= ຂວາ
    • ຊອກຫາດັດສະນີກາງຂອງຂໍ້ ຈຳ ກັດດັ່ງກ່າວ ກາງ = ຊ້າຍ + ຂວາ / 2
    • If a [ກາງ] == ເປົ້າ ໝາຍ, ກັບຄືນກາງ
    • ໃນກໍລະນີທີ່ມີມູນຄ່າຫຼາຍກວ່າເກົ່າ, ພວກເຮົາຍ້າຍໄປທາງຊ້າຍເຄິ່ງ ໜຶ່ງ ໂດຍໃຊ້ ຂວາ = ກາງ - 1 ແລະປະຫຍັດ ປີ = ກາງ
    • ນີ້ຈະເຮັດໃຫ້ເປັນກໍລະນີເມື່ອ a [ກາງ] <ເປົ້າ ໝາຍ, ພວກເຮົາຊ່ວຍປະຢັດ ປີ = ກາງ +1 ແລະຍ້າຍໄປຢູ່ເຄິ່ງຂວາມືໂດຍໃຊ້ left = ກາງ + 1
    • ຕອບກັບ
  5. ພິມຜົນໄດ້ຮັບ

ການຈັດຕັ້ງປະຕິບັດລະບົບ algorithm ເພື່ອຊອກຫາ Search Insert Position ຂອງ Target Leetcode Solution

ໂຄງການ C ++

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

int binarySearch(vector <int> &a , int target)
{
    int l = 0 , r = (int)a.size() - 1 , mid , ans = -1;
    while(l <= r)
    {
        mid = l + (r - l) / 2;
        if(a[mid] == target)
            return mid;
        if(a[mid] < target)
        {
            l = mid + 1;
            ans = mid + 1;
        }
        else
        {
            ans = mid;
            r = mid - 1;
        }
    }
    return ans;
}

int searchInsert(vector<int>& a, int target)
{
    return binarySearch(a , target);
}

int main()
{
    vector <int> a = {1 , 3 , 5 , 7 , 9};
    int target = 8;
    cout << searchInsert(a , target) << '\n';
}

Java Program

class search_insert_position
{
    static int binarySearch(int[] a , int target)
    {
        int l = 0 , r = a.length - 1 , mid , ans = -1;
        while(l <= r)
        {
            mid = l + (r - l) / 2;
            if(a[mid] == target)
                return mid;
            if(a[mid] < target)
            {
                l = mid + 1;
                ans = mid + 1;
            }
            else
            {
                ans = mid;
                r = mid - 1;
            }
        }
        return ans;
    }

    static int searchInsert(int[] a , int target)
    {
        return binarySearch(a , target);
    }

    public static void main(String args[])
    {
        int a[] = {1 , 3 , 5 , 7 , 9} , target = 8;
        System.out.println(searchInsert(a , target));
    }
}
4

ການວິເຄາະທີ່ສັບສົນໃນການຄົ້ນຫາການຊອກຫາການຊອກຫາ ຕຳ ແໜ່ງ ຂອງການແກ້ໄຂເປົ້າ ໝາຍ Leetcode

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

O (logN). ໃນກໍລະນີທີ່ຮ້າຍແຮງທີ່ສຸດ, ພວກເຮົາສາມາດເຮັດໄດ້ logN ການປຽບທຽບ.

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

ໂອ (1). ອີກເທື່ອຫນຶ່ງ, ພວກເຮົາໃຊ້ພື້ນທີ່ຄົງທີ່ ສຳ ລັບຕົວແປຕ່າງໆ.