ລວມການແກ້ໄຂ Leetcode Arrays Sorted  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg ByteDance Cisco eBay Expedia ເຟສບຸກ Goldman Sachs ກູໂກ IBM LinkedIn lyft Microsoft Netflix Oracle ຕາຕະລາງ Uber VMware Yahoo Yandex
ຂັ້ນຕອນວິທີ Array ລະຫັດ ການສໍາພາດ ການສໍາພາດກ່ອນ LeetCode LeetCodeSolutions ສອງຕົວຊີ້

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

ຍົກຕົວຢ່າງ  

{1 , 2 , 3 , - , - , -}
{2 , 6 , 7}
1 2 2 3 6 7
{1 , 1 , 1 ,  - , -}
{2 , 4}
1 1 1 2 4

ວິທີການ (ການຈັດຮຽງ)  

ພວກເຮົາສາມາດໂອນສ່ວນປະກອບທັງ ໝົດ ຂອງແຖວທີສອງໄປຫາໂຕ ທຳ ອິດ. ຈາກນັ້ນພວກເຮົາສາມາດຈັດຮຽງແຖວ ທຳ ອິດເພື່ອໃຫ້ໄດ້ຜົນທີ່ຕ້ອງການ.

ລະບົບວິເຄາະ

  1. ສຳ ລັບ i = 0 ເຖິງ i = N, ມອບ ໝາຍ
    1. a [i + m] = b [i], a = ແຖວ ທຳ ອິດ, ຂ = ແຖວທີສອງ
  2. ຈັດຮຽງແຖວ ທຳ ອິດ
  3. ພິມຜົນທີ່ຕ້ອງການ

ການປະຕິບັດການແກ້ໄຂບັນຫາເລຂາຄະນິດ Leetcode

ໂຄງການ C ++

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

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
    for(int i = 0 ; i < n ; i++)
        a[i + m] = b[i];

    sort(a.begin() , a.end());
    return;
}

int main()
{
    vector <int> a = {1 , 2 , 3};
    vector <int> b = {2 , 6 , 7};

    int m = 3 , n = 3;
    a.resize(m + n);
    merge(a , m , b , n);
    for(int &x : a)
        cout << x << " ";

    return 0;
}

ໂຄງການ Java

import java.util.Arrays;

class merge_sorted_array
{
    static void merge(int[] a , int m , int[] b , int n)
    {
        for(int i = 0 ; i < n ; i++)
            a[i + m] = b[i];
        Arrays.sort(a);
    }

    public static void main(String args[])
    {
        int m = 3 , n = 3;

        int[] a = new int[m + n];

        a[0] = 1;
        a[1] = 2;
        a[2] = 3;

        int[] b = {2 , 6 , 7};
        merge(a , m , b , n);

        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }
}
1 2 2 3 6 7

ການວິເຄາະຄວາມສັບສົນຂອງວິທີແກ້ໄຂບັນຫາ Leetcode

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

O (KlogK), ບ່ອນທີ່ K = N + M. N = ຂະ ໜາດ ຂອງຂບວນ ທຳ ອິດ, M = ຂະ ໜາດ ຂອງຂບວນທີສອງ. ດັ່ງທີ່ພວກເຮົາຈັດຮຽງແຖວ ທຳ ອິດຫຼັງຈາກທີ່ມັນເກັບ N + M ທັງ ໝົດ.

ເບິ່ງ
ວິທີແກ້ໄຂບັນຫາ Leetcode ທີ່ເພີ່ມຂື້ນເລື້ອຍໆ

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

O (1) ເປັນຄວາມຊົງຈໍາຄົງທີ່ຖືກນໍາໃຊ້ສໍາລັບການປ່ຽນແປງ.

ວິທີການ (ສອງຊີ້)  

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

ນີ້ຈະຕັດບັນຫາຂອງ“ ໜ່ວຍ ຄວາມ ຈຳ ພິເສດ” ຍ້ອນວ່າພວກເຮົາສືບຕໍ່ແກ້ໄຂບັນດາອົງປະກອບໃນຊ່ອງຫວ່າງ.

ລວມການແກ້ໄຂ Leetcode Arrays SortedPin

ລະບົບວິເຄາະ

  1. ເລີ່ມຕົ້ນສອງຕົວແປ i ແລະ j ເກັບຮັກສາຕົວຊີ້ວັດຂອງອົງປະກອບສຸດທ້າຍຂອງແຖວທີ ໜຶ່ງ ແລະທີສອງຕາມ ລຳ ດັບ.
    • i = M - 1, j = N - 1
  2. ເລີ່ມຕົ້ນຕົວແປ idx, ການເກັບຮັກສາດັດສະນີສຸດທ້າຍຂອງແຖວ ທຳ ອິດ, ນັ້ນແມ່ນ:
    • idx = N + M - 1
  3. ຕອນນີ້, ເຮັດສິ່ງຕໍ່ໄປນີ້ຈົນກ່ວາທັງສອງ i or j ກາຍເປັນສູນ
    • ຖ້າ a [i]> = b [j]
      • ມອບ ໝາຍ ໃຫ້ [idx] = a [i], ຫຼຸດລົງ i
    • ອື່ນ ໆ
      • ມອບ ໝາຍ ໃຫ້ [idx] = b [j], ຫຼຸດລົງ j
    • ຫຼຸດລົງ idx
  4. ທັງຂອງ i ຫຼື j ບໍ່ແມ່ນສູນ, ຊຶ່ງຫມາຍຄວາມວ່າບາງອົງປະກອບຍັງບໍ່ທັນຖືກລວມເຂົ້າກັນ. ຍ້ອນວ່າພວກເຂົາຈະຢູ່ໃນລັກສະນະທີ່ມີການຈັດລຽງ, ພວກເຮົາພຽງແຕ່ປະກອບໃຫ້ພວກມັນເຂົ້າໄປໃນແຖວ ທຳ ອິດຢູ່ທາງ ໜ້າ.
  5. ໃນຂະນະທີ່ i ບໍ່ໄດ້ກາຍເປັນສູນ,
    1. ມອບ ໝາຍ ໃຫ້ [idx] = a [i]
    2. ຫຼຸດລົງ idx ແລະ i
  6. ໃນຂະນະທີ່ j ບໍ່ໄດ້ກາຍເປັນສູນ,
    1. ມອບ ໝາຍ ໃຫ້ [idx] = b [j]
    2. ຫຼຸດລົງ idx ແລະ j
  7. ດຽວນີ້ຂບວນ ທຳ ອິດມີສ່ວນປະກອບທັງ ໝົດ ຕາມ ລຳ ດັບທີ່ຕ້ອງການ.

ການປະຕິບັດການແກ້ໄຂບັນຫາເລຂາຄະນິດ Leetcode

ໂຄງການ C ++

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

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
    int i = m - 1 , j = n - 1 , idx = m + n - 1;
    while(i >= 0 && j >= 0)
    {
        if(a[i] >= b[j])
        {
            a[idx] = a[i];
            i--;
        }
        else
        {
            a[idx] = b[j];
            j--;
        }
        idx--;
    }


    while(i >= 0)
        a[idx--] = a[i--];

    while(j >= 0)
        a[idx--] = b[j--];

    return;
}

int main()
{
    vector <int> a = {1 , 2 , 3};
    vector <int> b = {2 , 6 , 7};

    int m = 3 , n = 3;
    a.resize(m + n);
    merge(a , m , b , n);
    for(int &x : a)
        cout << x << " ";

    return 0;
}

ໂຄງການ Java

import java.util.Arrays;

class merge_sorted_array
{
    static void merge(int[] a , int m , int[] b , int n)
    {
        int i = m - 1 , j = n - 1 , idx = m + n - 1;
        while(i >= 0 && j >= 0)
        {
            if(a[i] >= b[j])
            {
                a[idx] = a[i];
                i--;
            }
            else
            {
                a[idx] = b[j];
                j--;
            }
            idx--;
        }

        while(i >= 0)
            a[idx--] = a[i--];

        while(j >= 0)
            a[idx--] = b[j--];

        return;
    }

    public static void main(String args[])
    {
        int m = 3 , n = 3;

        int[] a = new int[m + n];

        a[0] = 1;
        a[1] = 2;
        a[2] = 3;

        int[] b = {2 , 6 , 7};
        merge(a , m , b , n);

        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }
}
1 2 2 3 6 7

ການວິເຄາະຄວາມສັບສົນຂອງວິທີແກ້ໄຂບັນຫາ Leetcode

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

O (N + M). N = ຂະ ໜາດ ຂອງຂບວນ ທຳ ອິດ, M = ຂະ ໜາດ ຂອງຂບວນທີສອງ. ດັ່ງທີ່ພວກເຮົາຮວບຮວມອາຄານທັງສອງຄັ້ງ.

ເບິ່ງ
ພະລັງງານຂອງສີ່ວິທີແກ້ໄຂ Leetcode

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

ໂອ (1), ດັ່ງທີ່ພວກເຮົາເກັບຮັກສາອົງປະກອບທັງ ໝົດ ໄວ້ໃນແຖວ ທຳ ອິດ. ດັ່ງນັ້ນ, ສູດການຄິດໄລ່ແມ່ນ ໃນ​ສະ​ຖານ​ທີ່.