时间戳

首页 > 解决方案 > 从排序数组中删除重复项，不同代码方式的相同解决方案具有不同的输出

c++ - 从排序数组中删除重复项，不同代码方式的相同解决方案具有不同的输出

问题描述

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include "hello_world.h"


using namespace std;


class Solution1 {
public:
    int removeDuplicates(vector<int>& nums) {
        return distance(nums.begin(), removeDuplicates(nums.begin(), nums.end(), nums.begin()));
    }
    template<typename InIt, typename OutIt>
    OutIt removeDuplicates(InIt begin, InIt end, OutIt output){
        while(begin != end){
            *output++ = *begin;
            begin = upper_bound(begin, end, *begin);
        }

        return output;
    }

};


class Solution2 {
public:
    int removeDuplicates(vector<int>& nums) {
        vector<int>::iterator output = nums.begin();
        while(nums.begin() != nums.end()){
            *output++ = *nums.begin();
            nums.begin() = upper_bound(nums.begin(), nums.end(), *nums.begin());
        }

        return distance(nums.begin(), output);
    }
};


int main()
{
    //helloworld test;
    //test.print();
    int num[3] = {1,1,2};
    vector<int> nums(num, num + 3);

    Solution2 so;
    int a = so.removeDuplicates(nums);
    cout<<a<<endl;


    return 0;
}

在 main 函数中，当我使用类 solution1 时，代码可以从数组 [1 1 2] 中删除重复的数字，以输出 [1 2]。为了简化代码，我将解决方案1改为解决方案2，但解决方案2无法正确输出，有人知道原因吗？

标签： c++algorithmvectoriteratorunique

解决方案

在这个while循环中

    while(nums.begin() != nums.end()){
        *output++ = *nums.begin();
        nums.begin() = upper_bound(nums.begin(), nums.end(), *nums.begin());
    }

您总是nums.begin()在条件和此语句中使用迭代器

        *output++ = *nums.begin();

因为这个说法

        nums.begin() = upper_bound(nums.begin(), nums.end(), *nums.begin());

不会更改新调用返回的迭代器nums.begin()。

您需要在循环之前引入迭代器类型的变量，例如

auto it = nums.begin();

while( it != nums.end()){
    *output++ = *it;
    it = upper_bound( it, nums.end(), *it );
}

这是一个演示程序

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

int main() 
{
    std::vector<int> v = { 1, 2 };

    size_t i = 0;

    while ( v.begin() != v.end() )
    {
        v.begin() = std::upper_bound( v.begin(), v.end(), *v.begin() );

        if ( ++i == 10 ) break;
    }

    std::cout << "i = " << i << '\n';

    i = 0;

    auto it = v.begin();

    while ( it != v.end() )
    {
        it = std::upper_bound( it, v.end(), *it );

        if ( ++i == 10 ) break;
    }

    std::cout << "i = " << i << '\n';

    return 0;
}

它的输出是

i = 10
i = 2

要在循环后删除重复项，请使用成员函数 erase

nums.erase( output, nums.end() );

使用标准算法也可以做到这一点std::unique。例如

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

推荐阅读