Удаление повторяющихся элементов в массиве без сортировки - неправильный вывод

Question

Я пытался написать функцию для удаления повторяющихся элементов в массиве целых чисел без сортировки.

Для этой задачи я создал функцию с именем removeDuplicateElements, которая получает массив и его строку и возвращает новый динамически размещенный массив, который является копией исходного массива с удалением всех дублирующих элементов. Эта функция также возвращает по ссылке размер нового массива.

Я также использовал в своем коде функции, которые создают динамический массив и распечатывают его.

Вот мой код:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

void printArray(int *arr, int size);
int *buildArray(int size);
int *removeDuplicateElements(int *arr, int size, int *newSize);

void main() {
    int size,newSize;
    int *arr;
    int *newArr;

    printf("please enter a number for the size of array: ");
    scanf("%d", &size);
    printf("\nenter %d numbers: ", size);
    arr = buildArray(size);
    printf("\nthe array after removing the duplicate elements is: ");
    newArr = removeDuplicateElements(arr, size, &newSize);
    printArray(newArr, newSize);
    free(newArr);
    free(arr);
}

/* this function removes all duplicate elements in a given array */
int *removeDuplicateElements(int *arr, int size, int *newSize) {
    int *newArr;
    int count = size, i, j; 

    /* finding the new size of the original array with removal its duplicate elements */
    for (i = 1; i < size; i++) {  
        for (j = 0; j < size; j++)
            if (arr[i] == arr[j] && i != j) {
                count--;
                break;
            }
    }
    newArr = (int*)malloc(count * sizeof(int)); /* dynamically allocating the new array */

    count = 1;
    newArr[0] = arr[0];

    /*adding the elements in the new array without changing the order*/
    for (i = 1; i < size; i++) {
        for (j = 0; j < size; j++) {
            if (arr[i] == arr[j] && i != j) {
                break;
            }
            if (j == size - 1) {
                newArr[count] = arr[i];
                count++;
            }
        }
    }
    *newSize = count;     /* updating the size of the new array */
    return newArr;        /* returning the address of new array */
}

void printArray(int *arr, int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int *buildArray(int size) {
    int i;
    int *arr = (int*)malloc(size * sizeof(int));

    if (!arr) {
        printf("ERROR! Not enough memory!\n");
        exit(1);
    }

    for (i = 0; i < size; i++)
        scanf("%d", &arr[i]);

    return arr;
}

Я получил неправильный вывод для этого кода, и я не понимаю, почему

Например, для следующего массива с size=5: 1 1 3 1 3 Я получаю неправильный вывод 1, тогда как ожидаемый выход 1 3.

Любая помощь будет оценена.

Answer 1

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

int* removeDuplicateElements(int *arr, int size, int *newSize)
{    
int *newArr;
int count = size, i, j;
int index = 0;

/*finding the new size of the original array with removal its duplicate elements*/

for(i=0;i<size;i++)
{
    for (j = i+1; j < size; j++)
        if (arr[i] == arr[j] && arr[i] != 0xFFFF)
            {
                count--;
                arr[j] = 0xFFFF;

            }

}

printf("Size is %d \n", count);

newArr = (int*)malloc(count * sizeof(int));      /*dynamically allocating the new array*/

for(i=0;i<size;i++)
{
    if(arr[i] != 0xFFFF)
    newArr[index++] = arr[i];
}

*newSize = count;     /*updating the size of the new array*/
return newArr;        /*returning the address of new array*/

}

Answer 2

Сначала вы неправильно вычисляете размер нового массива. Для вашего примера ввода, когда вы смотрите на первые 3, он сканирует весь массив, чтобы увидеть, сколько 3, и находит 2, и приходит к выводу, что это дубликат. Затем он делает то же самое для второго 3. Таким образом, вы получите размер нового массива равным 1.

Вместо сканирования всего массива вам нужно сканировать массив только для элементов, предшествующих проверяемому. Так что-то вроде этого.

for(i=1;i<size;i++)
{
    for (j = 0; j < i; j++)
        if (arr[i] == arr[j])
        {
            count--;
            break;
        }
}

И для кода, который заполняет новый массив, та же проблема

for(i=1;i<size;i++)
{
    for (j = 0; j < i; j++)
        if (arr[i] == arr[j])
        {
            break;
        }
    if(j==i)
    {
        newArr[count++]=arr[i];
    }
}