მაქსიმალური მასივი ორი მოცემული მასივიდან, რომელიც შეკვეთის ერთნაირია


Რთული ტური საშუალო
ხშირად ეკითხებიან Accenture Amazon ადგილზე მიტანა ფაქტები Fourkites OYO ოთახები პუბლიკის საპიენტი Zoho
Array Hash

დავუშვათ, რომ გვაქვს ორი მთელი რიცხვი მასივი იგივე ზომის 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}

ორი მოცემული მასივიდან მაქსიმალური მასივის ალგორითმი, რითიც ერთნაირია

  1. ორივე მასივი გადააკეთეთ ვექტორი.
  2. დალაგეთ ორივე ვექტორი არაამაღლებული თანმიმდევრობით.
  3. ერთდროულად გაიარეთ ორივე ვექტორი და ორივე ვექტორის უფრო დიდი მნიშვნელობები დააჭირეთ რუქას ელემენტის სიხშირესთან ერთად.
  4. შექმენით ახალი ვექტორი "გამომავალი".
  5. შეამოწმეთ არის თუ არა საერთო ელემენტი ა რუკა შემდეგ მასივში, შემდეგ დაამატეთ ეს ელემენტი გამომავალ ვექტორში.
  6. შეამოწმეთ, თუ არსებობს საერთო ელემენტი რუქაზე და ასევე მასივში, შემდეგ, აირჩიეთ ისინი, რომელთა სიხშირეა 1 და დაამატეთ ისინი გამომავალ ვექტორში.
  7. დაბეჭდეთ შედეგიანი ვექტორი "გამომავალი".

განმარტება

ორივე მასივის ვექტორად გადაქცევა და მათი დალაგება კლების თანმიმდევრობით. ამით ჩვენ შეგვიძლია ორივე მასივის მნიშვნელობები მივიღოთ ვექტორში და თანმიმდევრობით უფრო დიდი რიცხვები გვაქვს ორივე ვექტორში. ასე რომ, ჩვენ შეგვიძლია ავირჩიოთ 'n' მაქსიმალური რიცხვი ორივე მასივიდან.

გაუმკლავდეს საერთო ელემენტების საქმეს, რის გაკეთებასაც ვაპირებთ, არის ერთდროულად შედარება ვექტორებისა და მაქსიმალური კრეფა ორივე მასივიდან, და მათი სიხშირით ჩასმა რუქაზე, ამით ჩვენ შეგვიძლია გავაგრძელოთ თვალი თუ შესაძლებელია ვიყოთ საერთო ელემენტები, ჩვენ მაქსიმალურ ელემენტებს ვუწევთ რუქას, თუ ერთ ელემენტზე მეტჯერ ვიპოვნეთ, ჩვენ უბრალოდ ვაპირებთ გავზარდოთ მათი სიხშირე და ისინი არ ჩაითვლება რუკაში დამატებით ელემენტებად, ისინი აღინიშნება როგორც სიხშირე 2, 3 ან მეტი. ამრიგად, მოგვიანებით გადაკვეთისას, ჩვენ შეგვიძლია მისი იგნორირება და პირველი მასივის პრიორიტეტიზაცია.

ჩვენ ვაპირებთ გადავკვეთოთ როგორც მასივები, ასევე რუკა. პირველი, ჩვენ უნდა გადავკვეთოთ პირველი მასივი რუქით, თუ რომელიმე საერთო ელემენტია ნაპოვნი როგორც რუკაზე, ასევე მასივში, ჩვენ უნდა გადავდოთ ის გამომავალ ვექტორში, რომელიც შედეგად შევქმენით. შემდეგ ჩვენ გადავკვეთთ მეორე მასივს, რადგან საერთო ელემენტის შენახვაც შესაძლებელია შედეგში, ამიტომ აქ, მეორე მასივის საერთო მნიშვნელობასთან და რუკასთან ერთად, ჩვენ ვაპირებთ შეამოწმოთ, აქვს თუ არა ამ ელემენტს სიხშირე 1-ზე , მაშინ მხოლოდ ჩვენ ვაბიძგებთ მას შედეგობრივ ვექტორში. დაბოლოს, დაბეჭდეთ ეს ვექტორი.

განხორციელება

C ++ პროგრამა ორი მოცემული მასივიდან მაქსიმალური მასივისთვის, რიგის იგივე შეკვეთისთვის

#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

ჯავა პროგრამა მაქსიმალური მასივისთვის ორი მოცემული მასივიდან, რომელიც შეკვეთის ერთნაირია

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]

სირთულის ანალიზი მაქსიმალური მასივისთვის ორი მოცემული მასივიდან, რომელიც წესრიგს ერთნაირად ინახავს

დროის სირთულე

O (n log n) სადაც "ნ" არის მასივების სიგრძე.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივების სიგრძე.