Array ສູງສຸດຈາກສອງ Arrays ການຮັກສາ Order Order ຄືກັນ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Accenture Amazon ເດລີ ປັດໃຈ ສີ່ພັນ ຫ້ອງ OYO Publicis Sapient Zoho
Array Hash

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

ຍົກຕົວຢ່າງ

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

int arr1 [] = {3,7,9,1,4}

int arr2 [] = {2,8,6,5,3}

ຜົນໄດ້ຮັບ:

{7, 9, 8, 6, 5}

ຄໍາອະທິບາຍ:

ໃນຖານະເປັນ 7, 9 ແມ່ນອົງປະກອບໃນແຖວ ທຳ ອິດ, ສະນັ້ນມັນຈະມາກ່ອນໃນຜົນຜະລິດ.

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

int arr1 [] = {9,3,2}

int arr2 [] = {6,4,1}

ຜົນໄດ້ຮັບ:

{9, 6, 4}

ສູດການຄິດໄລ່ ສຳ ລັບ Array ສູງສຸດຈາກສອງ Arrays ການຮັກສາ Order Order ຄືກັນ

  1. ປ່ຽນອາຄານທັງສອງເຂົ້າໄປໃນ vector.
  2. ຈັດຮຽງທັງສອງອັນຂອງ vector ຢູ່ໃນ ລຳ ດັບທີ່ບໍ່ໄດ້ຂື້ນໄປ.
  3. ລອກເສັ້ນ vector ທັງສອງພ້ອມກັນ, ແລະຍູ້ 'n' ຄຸນຄ່າທີ່ໃຫຍ່ກວ່າຂອງທັງສອງຂອງ vector ເຂົ້າໄປໃນແຜນທີ່ພ້ອມກັບຄວາມຖີ່ຂອງອົງປະກອບ.
  4. ສ້າງ vector ໃໝ່“ ຜົນຜະລິດ”.
  5. ກວດເບິ່ງວ່າມີອົງປະກອບທົ່ວໄປຢູ່ໃນ a ແຜນທີ່ ແລະຍັງຢູ່ໃນຂບວນ ທຳ ອິດ, ຈາກນັ້ນ, ຕື່ມອົງປະກອບນັ້ນເຂົ້າໄປໃນ vector ຜົນຜະລິດ.
  6. ກວດເບິ່ງ, ຖ້າມີສ່ວນປະກອບທົ່ວໄປໃນແຜນທີ່ແລະຍັງຢູ່ໃນແຖວທີສອງ, ຫຼັງຈາກນັ້ນ, ເລືອກເອົາຄວາມຖີ່ຂອງມັນທີ່ 1, ແລະເພີ່ມພວກມັນເຂົ້າໄປໃນ vector ຜົນຜະລິດ.
  7. ພິມ vector ຜົນທີ່ໄດ້ຮັບ.

ຄໍາອະທິບາຍ

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

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

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

ການປະຕິບັດ

ໂປຣແກຣມ C ++ ສຳ ລັບ Array ສູງສຸດຈາກສອງ Arrays Keeping Order ດຽວກັນ

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>

using namespace std;

void makeGreaterFirstArray(int A[], int B[], int n)
{
    vector<int> V1(A, A+n);
    vector<int> V2(B, B+n);
    sort(V1.begin(), V1.end(), greater<int>());
    sort(V2.begin(), V2.end(), greater<int>());

    unordered_map<int, int> MAP;
    int i = 0, j = 0;
    while (MAP.size() < n)
    {
        if (V1[i] >= V2[j])
        {
            MAP[V1[i]]++;
            i++;
        }
        else
        {
            MAP[V2[j]]++;
            j++;
        }
    }
    vector<int> output;
    for (int i = 0; i < n; i++)
        if (MAP.find(A[i]) != MAP.end())
            output.push_back(A[i]);

    for (int i = 0; i < n; i++)
        if (MAP.find(B[i]) != MAP.end() && MAP[B[i]] == 1)
            output.push_back(B[i]);

    for (int i = 0; i < n; i++)
        cout << output[i] << " ";
}
int main()
{
    int arr1[] = {3,7,9,1,4};
    int arr2[] = {2,8,6,5,3};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    makeGreaterFirstArray(arr1, arr2, n);
    return 0;
}
7 9 8 6 5

ໂປຣແກຣມ Java ສຳ ລັບ Array ສູງສຸດຈາກສອງ Arrays Keeping Order ດຽວກັນ

import java.util.Collections;
import java.util.Vector;
import java.util.HashMap;
import java.util.Arrays;
import java.util.stream.Collectors;

class findsubarray
{
    public static void makeGreaterFirstArray(int []A, int []B, int n)
    {
        Vector<Integer> V1 = new Vector<>();
        Vector<Integer> V2 = new Vector<>();

        Integer[] I1 = Arrays.stream( A ).boxed().toArray( Integer[]::new );
        Integer[] I2 = Arrays.stream( B ).boxed().toArray( Integer[]::new );


        Collections.addAll(V1, I1);
        Collections.addAll(V2, I2);

        Collections.sort(V1, Collections.reverseOrder());
        Collections.sort(V2, Collections.reverseOrder());


        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        int i = 0, j = 0;
        while (MAP.size() < n)
        {
            if (V1.get(i) >= V2.get(j))
            {
                if(MAP.containsKey(V1.get(i)))
                {
                    MAP.put(V1.get(i), MAP.get(V1.get(i))+1);
                    i++;
                }
                else
                {
                    MAP.put(V1.get(i),1);
                    i++;
                }
            }
            else
            {
                if(MAP.containsKey(V2.get(j)))
                {
                    MAP.put(V2.get(j), MAP.get(V2.get(j))+1);
                    j++;
                }
                else
                {
                    MAP.put(V2.get(j),1);
                    j++;
                }
            }
        }
        Vector<Integer> output = new Vector<Integer>();

        for (int a = 0; a < n; a++)
            if (MAP.containsKey(A[a]))
                output.add(A[a]);

        for (int b = 0; b < n; b++)
            if (MAP.containsKey(B[b]) && MAP.get(B[b])==1)
                output.add(B[b]);


        System.out.println(output);
    }
    public static void main(String [] args)
    {
        int arr1[] = {3,7,9,1,4};
        int arr2[] = {2,8,6,5,3};
        int n = arr1.length;
        makeGreaterFirstArray(arr1, arr2, n);
    }
}
[7, 9, 8, 6, 5]

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບ Array ສູງສຸດຈາກສອງ Arrays Keeping Order ດຽວກັນ

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

O (n log n) ບ່ອນທີ່ "n" ແມ່ນຄວາມຍາວຂອງຂບວນການ.

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

O (n) ບ່ອນທີ່ "n" ແມ່ນຄວາມຍາວຂອງຂບວນການ.