Réduire un tableau à au plus un élément par l'opération donnée

Dans ce problème, nous réduisons la taille du tableau à 1 ou 0 en effectuant l'opération donnée à chaque tour.

Nous pouvons trier le tableau à chaque tour pour obtenir le maximum d'éléments à chaque itération. De plus, nous pouvons également utiliser la structure de données principale pour améliorer les performances du code.

Énoncé du problème - On nous donne un tableau de nombres[]. Nous devons réduire le tableau en procédant comme suit.

• Sélectionnez les deux plus grands éléments du tableau.

• Si deux éléments sont identiques, supprimez les deux éléments du tableau.

• Si deux éléments ne sont pas identiques, supprimez les deux éléments du tableau et insérez abs(premier − secondaire) dans le tableau.

Imprimez le dernier élément du tableau. Si le tableau est vide, imprimez 0.

Exemple

Entrez

nums = {5, 9, 8, 3, 2, 5};

Sortie

0

Instructions

• Au premier tour, on prend 9 et 8 et on ajoute leur différence au tableau. Par conséquent, le tableau devient [5, 3, 2, 5, 1].

• Au deuxième tour on prend 5 et 5. Par conséquent, le tableau devient [3, 2, 1].

• Au prochain tour, on prend 3 et 2. Par conséquent, le tableau devient [1, 1]

• Au dernier tour, on prend 1 et 1. Par conséquent, le tableau devient vide et nous imprimons 0.

Entrez

nums = {5, 5, 5, 5, 5};

Sortie

5

Explication- On supprime deux fois une paire de 5, et un 5 reste dans le tableau.

Entrez

nums = {4, 8, 7, 6};

Sortie

1

Explication - Tout d'abord, nous sélectionnons 8 et 7. Par conséquent, le tableau devient [4, 1, 6]. Après cela, nous sélectionnons 4 et 6. Par conséquent, le tableau devient [1, 2]. Lors de la dernière opération, le tableau devient [1].

Méthode 1

Dans cette méthode, nous allons parcourir le tableau jusqu'à ce que la taille du tableau devienne 1 ou 0. À chaque itération, nous trierons le tableau et effectuerons l'opération donnée sur les 2 premiers éléments du tableau trié. Enfin, nous imprimerons la sortie en fonction de la taille du tableau.

Algorithme

Étape 1- Stockez la taille du tableau dans la variable "len".

Étape 2- Commencez à parcourir le tableau à l'aide d'une boucle while.

Étape 3- Utilisez la méthode sort() dans une boucle pour trier inversement le tableau.

Étape 4- Obtenez les premier et deuxième éléments du tableau. Calculez également la différence entre le premier et le deuxième élément du tableau.

Étape 5− Si la différence est de 0, supprimez les deux premiers éléments du tableau et réduisez 'len' de 2. Si la différence n'est pas 0, supprimez les 2 premiers éléments et décrémentez 'len' moins 1.

Étape 6- Enfin, si la taille du tableau est 0, renvoyez 0. Sinon, le premier élément du tableau est renvoyé.

Exemple

#include <bits/stdc++.h>
using namespace std;

int findLast(vector<int> &nums) {
    int len = nums.size();
    int p = 0;
    while (len > 1) {
        // Sort array in reverse order
        sort(nums.begin(), nums.end(), greater<int>());
        // Take the first and second elements of the array
        int a = nums[0];
        int b = nums[1];
        // Take the difference between the first and second element
        int diff = a - b;
        if (diff == 0) {
            nums.erase(nums.begin());
            nums.erase(nums.begin());
            len -= 2;
        } else {
            nums.erase(nums.begin());
            nums.erase(nums.begin());
            nums.push_back(diff);
            len -= 1;
        }
    }
    // When the size of the array is 0
    if (nums.size() == 0)
        return 0;
    return nums[0];
}
int main() {
    vector<int> nums = {5, 9, 8, 3, 2, 5};
    cout << "The last remaining element after performing the given operations is " << findLast(nums) << "\n";
    return 0;
}

Sortie

The last remaining element after performing the given operations is 0

Complexité temporelle - O(N*NlogN), où O(N) est utilisé pour parcourir le tableau et O(NlogN) est utilisé pour trier le tableau à chaque itération.

Complexité spatiale - O(N) pour trier le tableau.

Méthode 2

Dans cette méthode, nous utiliserons la file d'attente prioritaire, qui implémente la structure de données du tas. Il stocke toujours les éléments dans un ordre trié. On peut donc facilement supprimer les 2 premiers éléments les plus gros.

Algorithme

Étape 1- Définissez "p_queue" appelée file d'attente prioritaire.

Étape 2- Insérez tous les éléments du tableau dans la file d'attente prioritaire.

Étape 3- Répétez jusqu'à ce que la taille de la file d'attente prioritaire soit supérieure à 1.

Étape 4- Supprimez un par un les 2 premiers éléments de la file d'attente prioritaire.

Étape 5- Trouvez la différence entre deux éléments.

Étape 6- Si la différence n'est pas de 0, placez-la dans la file d'attente prioritaire.

Étape 7− Enfin, si la taille de la file d'attente est de 0, renvoyez 0.

Étape 8- Sinon, retournez l'élément en haut de la file d'attente.

Exemple

#include <bits/stdc++.h>
using namespace std;

int findLast(vector<int> &nums) {
    // Defining a priority queue
    priority_queue<int> p_queue;
    // Inserting array elements in priority queue
    for (int p = 0; p < nums.size(); ++p)
        p_queue.push(nums[p]);
    // Make iterations
    while (p_queue.size() > 1) {
        // Take the first element from queue
        int first = p_queue.top();
        p_queue.pop();
        // Get the second element from queue
        int second = p_queue.top();
        p_queue.pop();
        // Take the difference of first and second elements
        int diff = first - second;
        if (diff != 0)
            p_queue.push(diff);
    }
    // When queue is empty
    if (p_queue.size() == 0)
        return 0;
    // Return the last remaining element
    return p_queue.top();
}
int main() {
    vector<int> nums = {5, 9, 8, 3, 2, 5};
    cout << "The last remaining element after performing the given operations is " << findLast(nums) << "\n";
    return 0;
}

Sortie

The last remaining element after performing the given operations is 0

Complexité temporelle - La complexité temporelle de l'insertion et de la suppression d'éléments dans la file d'attente prioritaire est O(NlogN).

Complexité spatiale - O(N) pour stocker les éléments dans la file d'attente prioritaire.

La structure des données de la file d'attente prioritaire est toujours utile lorsque nous devons organiser les données du tableau dans un ordre spécifique après l'insertion ou la suppression d'un élément. Il implémente la structure de données en tas, permettant ainsi l'insertion et la suppression.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!