Удалить дублирующиеся числа в массиве в C:

Question

#include <stdio.h> 

int main() 
{ 
    int array[20], t = 0; //20-t is the new size of array. 

    for(int i = 0; i<20; i++) 
     scanf("%d", &array[i]); 

    for(int i = 0; i<20-t; i++) 
    { 
     for(int j = i+1; j<20-t; j++) 
     { 
      if(array[i] == array[j]) 
      { 
       for(int z = j; z<20-t; z++) 
        array[z] = array[z+1];//shift numbers. 
        t++; 
        i = -1; 
      } 
     } 
    } 
} 

Эта программа работает нормально, но я не уверен, почему она работает, когда i = -1, но не тогда, когда i = 0? Я также хотел бы знать сложность этого кода.

for(int i = 0; i<20-t; i++) 
    printf("%d ", array[i]); //Array after duplicates have been removed. 
    return 0; 
} 

Answer 1

Если написать программу следующим образом

#include <stdio.h> 

#define N 20 

int main(void) 
{ 
    int a[N]; 
    int n; 
    int i; 

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

    n = 0; 
    for (i = 0; i < N; i++) 
    { 
     int j = 0; 
     while (j < n && a[i] != a[j]) ++j; 
     if (j == n) a[n++] = a[i]; 
    } 

    for (i = 0; i < n; i++) printf("%d ", a[i]); 
    printf("\n"); 

    return 0; 
} 

тогда сложность алгоритма будет O (N^2).

Что касается вашего алгоритма, то его сложностью является O (N^3).

Это вы менее эффективны.

Answer 2

Прежде всего, ваши внутренние элементы доступа в цикле в [z, 20-t + 1], которые являются 1 элементом за пределами массива. Цикл «чисел сдвиг» должен быть:

for(int z = j; z<20-t-1; z++) 
    array[z] = array[z+1];//shift numbers. 

Чтобы ответить на ваш вопрос, он работает с i = -1, потому что i будет увеличиваться на петле для-у. Поэтому он будет 0 следующей итерацией (а не 1, тем самым пропуская 1 элемент).

Говорит, что, что вам нужно сделать, это уменьшает j итератора вместо, т.е .:

t++; --j; 

Он будет работать быстрее!