J'essaie d'éliminer les éléments dupliqués dans un vecteur trié de sorte que chaque élément apparaisse qu'une seule fois.
My Code: P>
The vector unique elements are: 0 1 2 3 4
3 Réponses :
Comment éliminer les doublons en place avec une complexité de temps de O (1)?
Vous ne pouvez pas. Même avec le vecteur trié, vous devez simplement comparer chaque élément à savoir s'il est unique ou non. O (n) est optimal.
Cependant, o (1) la complexité de temps n'était pas requise par la tâche non plus:
... avec
o (1) mémoire supplémentaire . Il n'y avait aucune mention de contrainte de complexité du temps - seule la complexité spatiale.
Vous pouvez la mettre en place en place (pas de mémoire supplémentaire) avec une complexité O (n) en utilisant simplement deux indices, une pour la lecture des éléments et une pour écrire.
#include <iostream>
#include <vector>
void removeDuplicates(std::vector<int> &nums)
{
unsigned int j = 1;
for (unsigned int i = 1; i < nums.size(); i++)
{
if(nums.at(i) != nums.at(i-1))
{
nums.at(j++) = nums.at(i);
}
}
nums.resize(j);
}
int main ()
{
std::vector <int> vect;
int arr[] = {0,0,1,1,1,1,1,2,2,3,3,4}; // the given array
int arrSize = sizeof(arr)/sizeof(arr[0]);
for (int i = 0; i <= arrSize-1; i++) // assign values to the vector
{
vect.push_back(arr[i]);
}
removeDuplicates(vect);
std::cout << "The unique vector elements are: ";
for (int i = 0; i < vect.size(); i++) {
std::cout << vect[i] << " ";
}
std::cout << "\n";
return 0;
}
Le moyen le plus simple de se débarrasser des duplicats est d'utiliser ce qui est déjà disponible dans la bibliothèque standard:
nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
Vous recherchez
std :: unique. Même si vous n'êtes pas autorisé à l'utiliser, vous pouvez étudier la manière dont elle est mise en œuvre.O (n) la complexité du temps serait bien, ce qui est demandé est O (1) espace supplémentaire; Pour le moment, votre complexité de temps est effectivement plus comme O (n²), comme chaque
efface en moyenne O (n) et votre complexité spatiale est O (n) pour le vecteur supplémentaire.La question ne vous demande pas d'avoir une complexité de temps (1) fois.
nums.erase (std :: unique (nums.begin (), nums.end (), nums.end ()); est ce que vous voulez.@Jesperjuhl c'est exactement ce que je cherchais. Notez, vous avez oublié un support. Il devrait être
nums.erase (std :: unique (nums.begin (), nums.end ()), nums.end ()); . Si vous pouvez écrire cela comme une réponse, je peux accepter votre réponse.