В чем ошибка этого кода?

Ваш код только проверяет, совпадает ли элемент в массиве со своим непосредственным предшественником.

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

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

Чтобы выполнить задание за время O (N log N), вы можете отсортировать массив, а затем использовать уже имеющуюся логику для удаления дубликатов из отсортированного массива. Очевидно, это полезно только в том случае, если вы в порядке с перестановкой чисел.

Если вы хотите сохранить исходный порядок, вы можете использовать что-то вроде хеш-таблицы или набора битов, чтобы отслеживать, было ли число уже просмотрено, и копировать каждое число в вывод только тогда / если оно еще не было просмотрено. Для этого меняем ваш текущий:

if (a[k] != a[i])
    a[k+1] = a[i];

примерно так:

if (!hash_find(hash_table, a[i])) { 
    hash_insert(hash_table, a[i]);
    a[k+1] = a[i];
}

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

С другой стороны, если вас больше волнует верхняя граница сложности, чем средний случай, вы можете использовать сбалансированную древовидную коллекцию вместо хеш-таблицы. Обычно это использует больше памяти и работает медленнее, но его ожидаемая сложность и сложность наихудшего случая практически идентичны (O (N log N)). Типичная хеш-таблица вырождается от постоянной сложности к линейной в худшем случае, что изменит вашу общую сложность с O (N) на O (N ²).

1. Сортировка кучи за время O (n log n).
2. Выполните итерации за O (n) раз, заменяя повторяющиеся элементы контрольным значением (например, INT_MAX).
3. Снова выполните сортировку кучи за O (n log n), чтобы выделить повторяющиеся элементы.

По-прежнему ограничен O (n log n).

Ваш код, по-видимому, требует, чтобы ввод был отсортирован. С несортированными входными данными, с которыми вы тестируете, ваш код не будет удалять все дубликаты (только соседние).

Вы можете получить решение O (N), если количество целых чисел известно заранее и меньше, чем объем памяти, который у вас есть :). Сделайте один проход, чтобы определить уникальные целые числа, которые у вас есть, используя вспомогательное хранилище, затем другой, чтобы вывести уникальные значения.

Код ниже написан на Java, но, надеюсь, вы уловили идею.

int[] removeRepeats(int[] a) {
    // Assume these are the integers between 0 and 1000
    Boolean[] v = new Boolean[1000]; // A lazy way of getting a tri-state var (false, true, null)

    for (int i=0;i<a.length;++i) {
       v[a[i]] = Boolean.TRUE;
    } 

    // v[i] = null => number not seen
    // v[i] = true => number seen

    int[] out = new int[a.length];
    int ptr = 0;
    for (int i=0;i<a.length;++i) {
        if (v[a[i]] != null && v[a[i]].equals(Boolean.TRUE)) {
            out[ptr++] = a[i];
            v[a[i]] = Boolean.FALSE;          
        }
    }

    // Out now doesn't contain duplicates, order is preserved and ptr represents how
    // many elements are set.
    return out;
}

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

Вы не получите O (N).

[РЕДАКТИРОВАТЬ] В статье, на которую вы ссылаетесь, предлагается отсортированный выходной массив, что означает, что поиск дубликатов в выходном массиве может быть двоичным поиском ... который равен O (LogN).

Ваша логика просто неверна, значит, неверен и код. Сделайте свою логику самостоятельно, прежде чем ее кодировать. Я предлагаю способ O (NlnN) с модификацией heapsort. С помощью heapsort мы соединяем от a [i] к [n], находим минимум и заменяем его на [i], верно? Итак, теперь модификация: если минимум совпадает с [i-1], то поменяйте местами минимум и [n], уменьшите номер элемента массива на 1. Это должно сработать за O (NlnN) способом.

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