Μεγιστοποιήστε τα στοιχεία χρησιμοποιώντας μια άλλη σειρά


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις αμαζόνα Φανατικοί Φουρκίτες
Παράταξη Χασίσι Ταξινόμηση

Ας υποθέσουμε, έχουμε δώσει δύο ακέραιους πίνακες του ίδιου μεγέθους n. Και οι δύο πίνακες περιέχουν θετικούς αριθμούς. Η δήλωση προβλήματος ζητά τη μεγιστοποίηση του πρώτου πίνακα χρησιμοποιώντας το δεύτερο στοιχείο πίνακα διατηρώντας τη δεύτερη σειρά ως προτεραιότητα (τα στοιχεία του δεύτερου πίνακα πρέπει να εμφανίζονται πρώτα στην έξοδο). Ο πίνακας που σχηματίζεται πρέπει να περιέχει n μοναδικά αλλά καλύτερα στοιχεία και των δύο συστοιχιών.

Παράδειγμα

arr1[] = {3,7,9,1,4}
arr2[] = {2,8,6,5,3}
{8, 6, 5, 7, 9}
arr1[] = {9,3,2}
arr2[] = {6,4,1}
{6, 4, 9}

Αλγόριθμος

  1. Δημιουργία ενός παράταξη μεγέθους 2 * n.
  2. Πρώτα αποθηκεύστε τα στοιχεία του δεύτερου πίνακα σε έναν πίνακα που δημιουργήθηκε και στη συνέχεια τα στοιχεία του πρώτου πίνακα.
  3. Ταξινόμηση του πίνακα σε μια μη αύξουσα ακολουθία.
  4. Αποθηκεύστε τις τιμές n του πίνακα στο σειρά.
  5. Τακτοποιήστε τα με τη σειρά καθώς έρχονται ως είσοδο λαμβάνοντας πρώτα το array2 και ελέγχοντας αν το στοιχείο του υπάρχει στο σύνολο και αποθηκεύστε τα στον τρίτο πίνακα από το 0th δείκτης.
  6. Επαναλάβετε την παραπάνω διαδικασία για τον πρώτο πίνακα.
  7. Εκτυπώστε τον πίνακα που προκύπτει.

εξήγηση

Έχουμε δύο ακέραιους αριθμούς παράταξη. Πρέπει να μεγιστοποιήσουμε τον πρώτο πίνακα με τέτοιο τρόπο ώστε ο πίνακας που σχηματίζεται να περιέχει το δεύτερο στοιχείο συστοιχίας πρώτα και μετά τον πρώτο πίνακα. Πρέπει να περιέχει το n μοναδικά και καλύτερα στοιχεία και από τις δύο συστοιχίες. Η σειρά πρέπει να διατηρηθεί, δηλαδή εάν το στοιχείο έρχεται πρώτο, θα πρέπει επίσης να έρχεται πρώτο στη δεύτερη σειρά. Για να το λύσετε, δημιουργήστε έναν πίνακα μεγέθους 2 * n επειδή έχουμε έναν πίνακα που δίνεται από το μέγεθος n και πρέπει απλώς να αποθηκεύσουμε τα στοιχεία και των δύο συστοιχιών.

Αποθηκεύστε τα στοιχεία του δεύτερου πίνακα πρώτα στον πίνακα που δημιουργήσαμε και, στη συνέχεια, αποθηκεύστε τα στοιχεία του πρώτου πίνακα στον πίνακα που δημιουργήθηκε. Το κάνουμε αυτό επειδή πρόκειται να εισαγάγουμε όλες τις τιμές του πίνακα που δημιουργήθηκε για να ορίσετε. Επειδή για να λύσουμε αυτόν τον κώδικα θα χρησιμοποιήσουμε ένα σετ. Μετά την εισαγωγή όλων των τιμών του πίνακα που δημιουργήθηκε στο σύνολο. Θα ταξινομήσουμε τον πίνακα σε μια μη αύξουσα ακολουθία.

Θα κάνουμε μια θέση στο Σετ για να εισάγουμε τις τιμές από τον πίνακα έως και n φορές. Το N times είναι, έχουμε ήδη τον ταξινομημένο πίνακα σε μη-αύξουσα ακολουθία, χρειαζόμαστε μόνο τα πρώτα n στοιχεία τώρα για να κάνουμε κάποιες λειτουργίες σε αυτό. Μετά την εισαγωγή του συνόλου, έχουμε τις μεγαλύτερες τιμές n στο σύνολο. Τώρα πρέπει να τακτοποιήσουμε αυτήν την τιμή σύμφωνα με τη σειρά τους καθώς εισέρχονται, οπότε θα διασχίσουμε τον πίνακα πρώτα, επειδή αυτός ο πίνακας είναι η προτεραιότητά μας. Αν λοιπόν βρήκαμε κάποιο από τα στοιχεία του πίνακα δεύτερη σε ένα σύνολο. Θα ενημερώσουμε αυτόν τον πίνακα που δημιουργήθηκε από την 0η θέση και επίσης θα ελέγξουμε και τον πρώτο πίνακα και θα ενημερώσουμε τις τιμές του στον πίνακα τρίτο.

Τώρα ενημερώστε τις τιμές του πίνακα3 στον πίνακα1 και στον πίνακα εκτύπωσης1 και έτσι μεγιστοποιούμε τον πρώτο πίνακα, παίρνοντας προτεραιότητα τον δεύτερο πίνακα.

Εκτέλεση

Πρόγραμμα C ++ για Μεγιστοποίηση Στοιχείων Χρησιμοποιώντας Άλλη Διάταξη

#include <iostream>
#include<algorithm>
#include<unordered_set>

using namespace std;

bool compare(int a, int b)
{
    return a > b;
}
void getMaximizeArray(int arr1[], int arr2[], int n)
{
    int arr3[2*n], j = 0;
    for (int i = 0; i < n; i++)
        arr3[j++] = arr1[i];
    for (int i = 0; i < n; i++)
        arr3[j++] = arr2[i];

    unordered_set<int> SET;

    sort(arr3, arr3 + 2 * n, compare);

    int i = 0;
    while (SET.size() != n)
    {
        if (SET.find(arr3[i]) == SET.end())
            SET.insert(arr3[i]);

        i++;
    }
    j = 0;
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr2[i]) != SET.end())
        {
            arr3[j++] = arr2[i];
            SET.erase(arr2[i]);
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr1[i]) != SET.end())
        {
            arr3[j++] = arr1[i];
            SET.erase(arr1[i]);
        }
    }
    for (int i = 0; i < n; i++)
        arr1[i] = arr3[i];
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr1[] = {3,7,9,1,4};
    int arr2[] = {2,8,6,5,3};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    getMaximizeArray(arr1, arr2, n);
    printArray(arr1, n);
}
8 6 5 7 9

Πρόγραμμα Java για μεγιστοποίηση στοιχείων χρησιμοποιώντας άλλη σειρά

import java.util.HashSet;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.lang.*;

class arrayMaximize
{
    public static void getMaximizeArray(int arr1[], int arr2[], int n)
    {
        int arr3[]=new int[2*n];
        int j = 0;
        for (int i = 0; i < n; i++)
            arr3[j++] = arr1[i];
        for (int i = 0; i < n; i++)
            arr3[j++] = arr2[i];


        Arrays.sort(arr3);

        HashSet<Integer> SET=new HashSet<>();

        int i = (2*n)-1;
        while (SET.size() != n)
        {
            if (!SET.contains(arr3[i]))
                SET.add(arr3[i]);

            i--;
        }


        j = 0;
        for (int a = 0; a < n; a++)
        {
            if (SET.contains(arr2[a]))
            {
                arr3[j++] = arr2[a];
                SET.remove(arr2[a]);
            }
        }

        for (int b = 0; b < n; b++)
        {
            if (SET.contains(arr1[b]))
            {
                arr3[j++] = arr1[b];
                SET.remove(arr1[b]);
            }
        }
        for (int c = 0; c < n; c++)
            arr1[c] = arr3[c];
    }
    public static void printArray(int arr[], int n)
    {
        for (int k = 0; k < n; k++)
            System.out.print(arr[k]+" ");
    }
    public static void main(String [] args)
    {
        int arr1[] = {3,7,9,1,4};
        int arr2[] = {2,8,6,5,3};
        int n = arr1.length;
        getMaximizeArray(arr1, arr2, n);
        printArray(arr1, n);
    }
}
8 6 5 7 9

Ανάλυση πολυπλοκότητας για μεγιστοποίηση στοιχείων χρησιμοποιώντας άλλη σειρά

Χρόνος πολυπλοκότητας

O (n * log n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.

Διαστημική πολυπλοκότητα

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.

αναφορές