Хоёр дараалсан массиваас дарааллыг ижил байлгах массивын дээд хэмжээ  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Accenture Амазоны Дели Мэдээллийн багц Фуркайт OYO өрөөнүүд Publicis Sapient Zoho
Array Хаш

Бидэнд хоёр бүхэл тоо байна гэж бодъё массив ижил хэмжээтэй Массивын аль аль нь нийтлэг тоонуудыг агуулж болно. Асуудлын шийдэл нь массивын хоёроос хамгийн их утгыг агуулсан үр дүнгийн массив үүсгэхийг хүсдэг. Эхний массивыг эрэмбэлэх хэрэгтэй (эхний массивын элементүүд гаралтанд хамгийн түрүүнд гарч ирэх ёстой). Гаралтын массив нь өгөгдсөн массивын аль алиных нь хамгийн их элемент байх боловч нийтлэг элементүүд нэг удаа орж массивыг нэн тэргүүнд эрэмбэлэх ёстой.

Жишээ нь  

Орц:

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" -ийг сонгож болно хамгийн их тоо массивын аль алинаас нь.

Бидний хийх гэж байгаа нийтлэг элементүүдийн хэргийг зохицуулахын тулд векторуудыг харьцуулж, массивын аль алинаас нь хамгийн ихийг нь сонгож, тэдгээрийн давтамжаар газрын зураг дээр байрлуулж, хэрэв боломжтой бол бид анхаарлаа хандуулж чадна. нийтлэг элементүүд байх болно, бид 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

Захиалгыг ижил байлгах XNUMX өгөгдсөн массиваас хамгийн дээд массивын Java програм

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) хаана "N" массивын урт юм.

мөн үзнэ үү
Массив дахь хамгийн их зай

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" массивын урт юм.