удалить дубликаты из отсортированного массива, то же решение с другим способом кода имеет другой вывод - PullRequest
Новая
       12

удалить дубликаты из отсортированного массива, то же решение с другим способом кода имеет другой вывод

1 голос
/ 27 января 2020 
#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;
}

В основной функции, когда я использую класс solution1, код может удалить дубликаты чисел из массива [1 1 2], чтобы вывести [1 2]. Чтобы упростить код, я изменил решение1 на решение2, но решение2 не может выполнить правильный вывод, кто-нибудь знает причину?

1 Ответ

2 голосов
/ 27 января 2020

В то время как l oop

    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().

Вам необходимо ввести переменную типа итератора перед l oop, например 

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

Для удаления дубликатов после l oop используйте функцию-член erase, например 

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

То же самое можно сделать с помощью стандартного алгоритма std::unique. Например 

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