Как возможно удалить дубликаты чисел в массиве?

Question

Задание: Удалить дубликаты чисел в массиве без использования сторонних библиотек. Пример: Для массива вида [1,3,3,3,6], программа должна вывести массив [1,3,6].

Моё решение:

#include <iostream>
using namespace std;
int main() {
    int num;
    cin >> num;
    int *arr = new int[num];
    for (int i = 0; i < num; i ++){
        int x;
        cin >> x;
        arr[i] = x;
    }
    int len_arr = num;
    for (int i = 0; i < len_arr; i ++){
        for (int j = i + 1; j < len_arr; j ++){
            if (arr[i] == arr[j]){
                arr[i] = arr[j];
                arr[j] = arr[j + 1];
                len_arr --;
            }
        }
    }

    for (int i = 0; i < len_arr; i ++){
        cout << arr[i] << " ";
    }

}

К сожалению работает только для массива вида [1, 3, 3, 6]. Если в массиве три дубликата, то программа начинает очень странно работать.

Answer 1

Когда вы нашли очередной дубликат, нужно сдвинуть все элементы массива с позиции j+1 до конца влево на один элемент, что эквивалентно удалению элемента из массива.

#include <iostream>
using namespace std;

int main() {

    int arr[] = {1, 3, 3, 3, 6};
    size_t len_arr = std::size(arr);
    for (size_t i = 0; i < len_arr; i ++){
        for (size_t j = i + 1; j < len_arr; j ++){
            if (arr[i] == arr[j]){
                
                for (size_t k = j; k < len_arr - 1; k++){
                    arr[k] = arr[k + 1];
                }
                len_arr--;
                j--; //так как элемент удалён, то на позицию j установился уже другой элемент, и его заново надо будет сравнить
            }
        }
    }

    for (size_t i = 0; i < len_arr; i ++){
        cout << arr[i] << " ";
    }

}

https://onlinegdb.com/TrI9C4-IY

А вот пример с использованием стандартной библиотеки:

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

int main() {

    int arr[] = {1, 3, 3, 3, 6};
    std::sort(std::begin(arr), std::end(arr));
    auto last = std::unique(std::begin(arr), std::end(arr));

    for (auto it = std::begin(arr); it < last; it ++){
        cout << *it << " ";
    }
    return 0;
}

https://onlinegdb.com/VdCoNaNT3

Порядок элементов во втором случае будет нарушен, так что эти два примера не эквивалентны. Вот пример эквивалентного кода без нарушения порядка:

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

int main() {

    int arr[] = {1, 3, 3, 3, 6};
    
    auto last = std::end(arr);
    for (auto it = std::begin(arr); it < last; it++)
    {
        last = std::remove(std::next(it), last, *it);
    }
    for (auto it = std::begin(arr); it < last; it ++){
        cout << *it << " ";
    }
    return 0;
}

https://onlinegdb.com/PBj6kOWMZ

Answer 2

@maestro предложил отличный вариант, но вы так же можете идя по массиву записывать все числа в set (не уверен, что это не сторонняя библиотека в вашей терминологии. Если не подходит, то как минимум ознакомьтесь с этим инструментом):

             #include <set>
             ...
             std :: set <int> uniqArr;
             for(int i = 0; i < num; ++i){
                 uniqArr.emplace(arr[i]);
             }

set - специальная структура данных, которая хранит уникальные значения в отсортированном виде. Вы можете самостоятельно разработать свой класс set,это будет очень полезно для вашего образования, даже если реализуете только основную концепцию и не все методы.

Answer 3

Опоздал, но раз уж написал - выложу. Тот же принцип, что у maestro, поменьше копирований за счёт того, что элемент за одну операцию ставится на нужное место.

int num = 8;

int arr[] = { 1, 3, 3, 6, 3, 6, 2, 3 };
int bad = 0;
for (int i = 0; i < num; i++) {
    for (int j = 0; j < i - bad; j++) {
        if (arr[i] == arr[j]) {
            bad++;
            break;
        }
    if (bad)
        arr[i - bad] = arr[i];
    }
}
for (int i = 0; i < num - bad; i++)
    std::cout << arr[i] << " ";

БЛОГ НА HUSL

Как возможно удалить дубликаты чисел в массиве?

Ответы (3 шт):