代码之家 › 专栏 › 技术社区 › csg techguy18985

在给定一个带有O(1)额外内存的排序向量的情况下,就地删除重复的元素。

time-complexity duplicates vector c++11 c++

-2

csg techguy18985 · 技术社区 · 6 年前

我试图删除排序向量中的重复元素,这样每个元素只出现一次。

我的代码:

#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)额外内存就地修改输入数组。

在我的代码中,大的O时间复杂性是O(N)。

如何在额外内存为O(1)的情况下将重复项移除到位?

3 回复 | 直到 6 年前

Jesper Juhl 6 年前

消除重复的最简单方法是使用标准库中已有的内容:

nums.erase(std::unique(nums.begin(), nums.end()), nums.end());

eerorika 6 年前

在时间复杂度为O(1)的情况下,如何在适当的位置删除重复项?

你不能。即使向量排序,你也必须简单地比较每个元素,以知道它是否唯一。O(N)是最优的。

但是,O(1)时间复杂性也不是任务所必需的:

…具有 o(1)额外内存 .

没有提到时间复杂性约束——只有空间复杂性。

Damien 6 年前

只需使用两个索引(一个用于读取元素,一个用于写入),就可以在复杂度为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;
}