Удалите дублирующиеся элементы на месте, учитывая отсортированный вектор с O (1) дополнительной памятью - PullRequest
Новая
       38

Удалите дублирующиеся элементы на месте, учитывая отсортированный вектор с O (1) дополнительной памятью

0 голосов
/ 20 января 2019

Я пытаюсь удалить повторяющиеся элементы в отсортированном векторе, чтобы каждый элемент появлялся только один раз.

Мой код: 

#include <iostream>
#include <vector>
using namespace std;

void removeDuplicates(vector<int> &nums)
{
    vector<int>::iterator it;
    unsigned int j = 1;

    while(j < nums.size()-1)
    {
        if(nums.at(j) == nums.at(j-1))
        {
            it = nums.begin()+j;
            nums.erase(it);
            --j;            // for every removal, correct the index
        }
        j += 1;             // increment the index
    }
}

int main ()
{
    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);

    cout << "The unique vector elements are: ";
    for (int i = 0; i < vect.size(); i++)
    {
        cout << vect[i] << " ";
    }
    cout << endl;

    return 0;
}

Когда я запускаю код, вывод

 The vector unique elements are: 0 1 2 3 4

Вопрос дает следующую инструкцию:

Не выделяйте дополнительное пространство для другого массива, вы должны сделать это, изменив входной массив на месте с помощью O (1) дополнительная память.

В моем коде сложность времени Big O равна O (n).

  • Как удалить дубликаты на месте с помощью дополнительной памятииз O (1)?

Ответы [ 3 ]

0 голосов
/ 20 января 2019

Вы можете реализовать его на месте (без дополнительной памяти) со сложностью O (n), просто используя два индекса, один для чтения элементов и один для записи. 

#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;
}
0 голосов
/ 21 января 2019

Самый простой способ избавиться от дубликатов - это использовать то, что уже доступно в стандартной библиотеке: 

nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
0 голосов
/ 20 января 2019

Как можно удалить дубликаты на месте с временной сложностью O (1)?

Ты не можешь. Даже с отсортированным вектором вы просто должны сравнить каждый элемент, чтобы узнать, является ли он уникальным или нет. O (N) является оптимальным.

Однако, сложность времени O (1) также не требовалась задачей:

... с O (1) дополнительной памятью .

Не было упоминания об ограничении сложности времени - только сложность пространства.

...