Удалить дубликаты из массива C ++ - PullRequest
Новая
       6

Удалить дубликаты из массива C ++

0 голосов
/ 10 октября 2018

Я пытаюсь создать простую программу, которая вызывает 2 функции.Первая функция принимает частично заполненный массив, проходит по нему и удаляет любые повторяющиеся значения.Когда значение удаляется из массива, оставшиеся числа перемещаются назад, чтобы заполнить пробел, т.е. когда функция завершается, все нулевые значения массива будут вместе в конце.

Вторая функция печатает обновленный массив.

Мой текущий код указан ниже.В настоящее время, когда я запускаю свой код, консоль показывает: 2 6 0 -858993460 -858993460 -858993460 -858993460 -858993460 -858993460 -858993460.Должно отображаться: 1 2 5 6, если он работал правильно.

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

#include "pch.h"
#include <iostream>
using namespace std;
void deleteRepeats(int *arr, int arraySize, int& posUsed);
void printArray(int *arr, int arraySize);

int main()
{
int arr[10] = { 1, 2, 2, 5, 6, 1};
int posUsed = 6;
int arraySize = 10;


deleteRepeats(arr, arraySize, posUsed);
printArray(arr, arraySize);

return 0;
}

void deleteRepeats(int *arr, int arraySize, int& posUsed)
{
{
    for (int i = 0; i < arraySize; i++)
    {
        for (int j = i; j < arraySize; j++)
        {
            if (arr[i] == arr[j])
            {
                for (int k = j; k < arraySize; k++)
                {
                    arr[k] = arr[k + 1];

                }
                posUsed--;

            }
            else
                j++;
        }
    }
}
}

void printArray(int *arr, int arraySize)
{
for (int i = 0; i < arraySize; i++)
{
    cout << arr[i] << "  ";
}
}

Ответы [ 3 ]

0 голосов
/ 10 октября 2018

Может быть проще представить алгоритм, имеющий отдельные входные и выходные массивы.Затем в псевдокоде: 

for i = 0 to input_array_size-1
    Is input[i] equal to input[j] for any j between 0 and i-1?
    Yes - do nothing
    No - copy input[i] to output

Для реализации этого с общим вводом и выводом вам нужно иметь два размера массива, input_array_size и output_array_size.Затем псевдокод становится 

output_array_size = 0
for i = 0 to input_array_size-1
    Is array[i] equal to array[j] for any j between 0 and output_array_size-1?
    Yes - do nothing
    No:
        copy array[i] to array[output_array_size]
        Increase output_array_size

Примечание. Он записывает выходные данные там, где был вход, поэтому проверка на наличие дубликатов должна проверять все элементы, которые были выведены.Например, если ваш массив равен 1, 2, 1, 3, 5, 6, 3, то для последнего 3 накопленный результат равен 1, 2, 3, 5, 6, и код должен сравнить все это с текущим элементом.

Для упрощения отладкигде написано «ничего не делать», вы можете установить текущий элемент в -1.Таким образом, если вы напечатаете ваш массив во время выполнения (для отладки), вам будет понятнее, какие элементы были удалены.

0 голосов
/ 10 октября 2018

Учитывая ваши ограничения присваивания (более C-like, чем идиоматический C ++), вы можете переписать вашу функцию так, чтобы она работала: 

void deleteRepeats(int *arr, int arraySize, int& posUsed)
{
    for (int i = 0; i < posUsed; ++i)
    {
        int duplicates = 0;
        int j = i + 1;
        // find the first duplicate, if exists
        for ( ; j < posUsed; ++j)
        {
            if ( arr[i] == arr[j] ) {
                ++duplicates;
                break;
            }
        }
        // overwrite the duplicated values moving the rest of the elements...
        for (int k = j + 1; k < posUsed; ++k)
        {
            if (arr[i] != arr[k])
            {
                arr[j] = arr[k];
                ++j;
            }
            // ...but skip other duplicates
            else
            {
                ++duplicates;    
            }
        }
        posUsed -= duplicates;
    }
    // clean up (could be limited to the duplicates only)
    for (int i = posUsed; i < arraySize; ++i)
        arr[i] = 0;
}
0 голосов
/ 10 октября 2018

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

  • Сортировать вектор
  • Используйте erase и unique для удаления дубликатов.

Вот код 

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

void print(std::vector<int> arr){
    for (const auto i : arr){
        std::cout << i <<" ";
    }
    std::cout <<"\n";
}

int main() {
    std::vector<int> arr{1, 2, 2, 5, 6, 1};    
    print(arr);

    sort( arr.begin(), arr.end() );
    arr.erase( unique( arr.begin(), arr.end() ), arr.end() );

    print(arr);
}

Ps.Использование int *arr, int arraySize не очень похоже на C ++.Пожалуйста, всегда старайтесь использовать правильный контейнер (который почти всегда будет std::vector).

РЕДАКТИРОВАТЬ: Я немного изменил свой ответ, потому что я нашел это сравнение скорости (и фактически весь ответ на вопрос). Какой самый эффективный способ удаления дубликатов и сортировки вектора?

...