ຜະສົມຜະສານແຖວສອງແຖວ  


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

ຖະແຫຼງການບັນຫາ  

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

ຍົກຕົວຢ່າງ  

ການປ້ອນຂໍ້ມູນ

A [] = {1, 3, 5, 7, 9}

B [] = {2, 4, 6, 8, 10}

ຜົນຜະລິດ

A [] = {1, 2, 3, 4, 5}

B [] = {6, 7, 8, 9, 10}

ຄໍາອະທິບາຍ

ລວມແຖວ = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

ຕອນນີ້ພວກເຮົາຈັດແຈງພວກມັນຕາມຂະ ໜາດ ຂອງອາເລທີ່ໃຫ້. ອົງປະກອບ n ທຳ ອິດໃນແຖວ ທຳ ອິດແລະອົງປະກອບ m ຕໍ່ໄປໃນແຖວທີສອງ.

ສະນັ້ນ, ສຸດທ້າຍອາຄານຈະເປັນ -

A [] = {1, 2, 3, 4, 5}

B [] = {6, 7, 8, 9, 10}

ລະບົບວິເຄາະ  

ຖ້າອາພາດເມັນປ້ອນຂໍ້ມູນແມ່ນ A ແລະ B

1. ດໍາເນີນການ loop ຜ່ານຂບວນ B ຈາກອົງປະກອບສຸດທ້າຍ. ໃນ (B []) ສຳ ລັບທຸກໆ B [i]

2. ປຽບທຽບອົງປະກອບທີ່ເລີ່ມຕົ້ນຈາກແຖວສຸດທ້າຍ A ກັບອົງປະກອບສຸດທ້າຍຂອງ B ແລະຖ້າພົບວ່າອົງປະກອບໃດພົບ ໜ້ອຍ ກວ່າອົງປະກອບສຸດທ້າຍຂອງ B. last = A [i], ຊອກຫາ A [j] <B [i].

  • ຍ້າຍອົງປະກອບທັງ ໝົດ ໄວ້ໃນ ຕຳ ແໜ່ງ ຂ້າງ ໜ້າ ຕິດກັບສ່ວນປະກອບທີ່ພົບໃນຂ.
  • A [j + 1] = A [j]
  • ທົດແທນອົງປະກອບຕໍ່ໄປຂອງອົງປະກອບທີ່ພົບກັບອົງປະກອບຈາກຂ.
  • A [j + 1] = B [i]
  • ປັບປຸງອົງປະກອບໃນ B, B [i] = ສຸດທ້າຍ
ເບິ່ງ
ຊອກຫາສາມອົງປະກອບຈາກສາມອາຄານທີ່ແຕກຕ່າງກັນດັ່ງກ່າວວ່າ a + b + c = ຜົນລວມ

3. ນຳ ໃຊ້ ໜ້າ ທີ່ໃນຫົວຂໍ້ການປ້ອນຂໍ້ມູນທີ່ໃຫ້ໄວ້, ແລະພິມປ້າຍ.

ການປະຕິບັດ  

ໂປຣແກຣມ C ++ ສຳ ລັບການລວມກຸ່ມແຖວສອງແຖວ

#include <bits/stdc++.h>
using namespace std;
//Merge function, arrays are A[],B[] and sizes M and N respectively
void Merge(int A[], int B[], int M, int N)
{
    //for all elements in B from last
    for(int i=N-1; i>=0; i--)
        {
            int j, last = A[M-1];
            // Moving elements one position ahead.
            for(j=M-2;j >= 0 && A[j]>B[i];j--)
                {
                    A[j+1] = A[j];
                }
            //Move next element and update element in B
            if(j!=M-2 || last > B[i])
                {
                    A[j+1] = B[i];
                    B[i] = last;
                }
        }
}
//function to print the given array
int PrintArray(int array[],int N)
{
    for (int i=0; i<N; i++)
       {
           cout <<array[i]<<" ";
       }
}
//Main function: To call functions on input array
int main(void)
{
    int A[] = {1, 3, 5, 7, 9};
    int B[] = {2, 4, 6, 8, 10};
    int M = sizeof(A)/sizeof(A[0]);
    int N = sizeof(B)/sizeof(B[0]);
    cout << "Input Arrays:-";
    cout << "\nArray A: ";
    PrintArray(A,M);
    cout << "\nArray B: ";
    PrintArray(B,N);
   
   //Mergeing A, B according to the condition
    Merge(A, B, M, N);
    
    cout << "\nAfter Merge:-";
    cout << "\nArray A: ";
    PrintArray(A,M);
    cout << "\nArray B: ";
    PrintArray(B,N);
    return 0;
}
Input Arrays:-
Array A: 1 3 5 7 9 
Array B: 2 4 6 8 10 
After Merge:-
Array A: 1 2 3 4 5 
Array B: 6 7 8 9 10

Java Program for merge Two Sorted Arrays

import static java.lang.Math.pow;
import java.util.Scanner;
class sum
{
    //Merge function, arrays are A[],B[] and sizes M and N respectively
    public static void Merge(int A[], int B[], int M, int N)
    {
        //for all elements in B from last
        for(int i=N-1; i>=0; i--)
            {
                int j, last = A[M-1];
                // Moving elements one position ahead.
                for(j=M-2;j >= 0 && A[j]>B[i];j--)
                    {
                        A[j+1] = A[j];
                    }
                //Move next element and update element in B
                if(j!=M-2 || last > B[i])
                    {
                        A[j+1] = B[i];
                        B[i] = last;
                    }
            }
    }
    //function to print the given array
    public static void PrintArray(int array[],int N)
    {
        for (int i=0; i<N; i++)
           {
               System.out.print(array[i]+" ");
           }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int m = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int b[] = new int[n];
        for(int i=0;i<n;i++)
        {
            b[i] = sr.nextInt();
        }
        //Mergeing A, B according to the condition
        Merge(a, b, n, m);
        System.out.println("\nAfter Merge:-");
        System.out.print("\nArray A: ");
        PrintArray(a,n);
        System.out.print("\nArray B: ");
        PrintArray(b,m);
        System.out.println();
    }
}
5 5
1 3 5 7 9
2 4 6 8 10
After Merge:-

Array A: 1 2 3 4 5 
Array B: 6 7 8 9 10

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການລວມຕົວແຖວສອງແຖວ  

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

O (n + ມ) ບ່ອນທີ່ n ແມ່ນຂະ ໜາດ ຂອງຂບວນ ທຳ ອິດແລະ m ແມ່ນຂະ ໜາດ ຂອງຂບວນທີສອງ. ໃນທີ່ນີ້ພວກເຮົາພຽງແຕ່ຜ່ານສ່ວນປະກອບທັງ ໝົດ ຂອງທັງສອງຂບວນນັ້ນເປັນເຫດຜົນທີ່ເຮັດໃຫ້ເຫດຜົນນີ້ເຮັດໃຫ້ພວກເຮົາສັບສົນກັບເວລາ O (n + m)

ເບິ່ງ
ຈັດລຽງລໍາດັບອີກເທື່ອ ໜຶ່ງ ເຖິງແມ່ນວ່າອົງປະກອບດັດສະນີມີຂະ ໜາດ ນ້ອຍກວ່າແລະອົງປະກອບດັດສະນີກໍ່ໃຫຍ່ກວ່າ

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

O (1) ເນື່ອງຈາກວ່າໃນທີ່ນີ້ພວກເຮົາບໍ່ໄດ້ໃຊ້ບ່ອນຊ່ວຍຫຍັງຢູ່ທີ່ນີ້. ພຽງແຕ່ແທນຄຸນຄ່າຈາກ ຕຳ ແໜ່ງ ໜຶ່ງ ໄປອີກ ຕຳ ແໜ່ງ ໜຶ່ງ.

ເອກະສານ