Что за ошибка в этом коде? - PullRequest
Новая
       10

Что за ошибка в этом коде?

2 голосов
/ 17 июля 2011

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

int remove_repeat(int *a, int n)
{
    int i, k;

    k = 0;
    for (i = 1; i < n; i++)
    {
        if (a[k] != a[i]) 
        {
            a[k+1] = a[i];
            k++;            
        }
    }
    return (k+1);
}

main()
{
    int a[] = {1, 4, 1, 2, 3, 3, 3, 1, 5};
    int n;
    int i;

    n = remove_repeat(a, 9);

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


}

1] Что неправильно в приведенном выше коде для удаления дубликатов.

2] Любое другое решение O (N) или O (NlogN) для этой проблемы. Его логика?

Ответы [ 7 ]

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

Все еще ограничен O (n log n).

1 голос
/ 17 июля 2011

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

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

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

Чтобы выполнить задание за 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 2 ).

1 голос
/ 17 июля 2011

Вы можете получить решение 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;
}
1 голос
/ 17 июля 2011

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

1 голос
/ 17 июля 2011

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

Вы не собираетесь получить O (N).

[EDIT] В статье, на которую вы ссылались, предлагается отсортированный выходной массив, который означает, что поиск дубликатов в выходном массиве может быть двоичным поиском ... который является O (LogN).

0 голосов
/ 17 июля 2011

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

0 голосов
/ 17 июля 2011

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

...