Удалить дубликат из массива - PullRequest
0 голосов
/ 13 января 2010

Мне нужно удалить повторяющиеся записи из массива, но я не могу использовать какие-либо новые структуры данных, и тот же массив должен возвращать только отдельные элементы.Например, если мой массив равен 1,3,3,3,5,55,67,1, то результат должен быть 1,3,5,55,67.

. Мне кажется, я решил проблему, но мне нужно ваше мнение о том, является ли это хороший алгоритм или мне нужноизменить что-то.

public void DeleteDuplicate(int[] array)
{
    int l = 0;
    int newPosition = array.Length -1;
    for (int i = 0; i < array.Length; i++)
    {
        for (int j = i + 1; j < array.Length-l; j++)
        {
            if (array[i] == array[j])
            {
                int temp = array[j];
                array[j] = array[newPosition];
                array[newPosition] = temp;
                newPosition--;
                l++;
            }
        }
    }
    Array.Resize(ref array, array.Length - l);
}

Ответы [ 3 ]

3 голосов
/ 13 января 2010

В общем вопрос, нужно ли поддерживать относительный порядок элементов. Например, можно ли вернуть {1, 2} для ввода {2, 1, 2, 1}.

Если это разрешено, то самым быстрым решением будет:

  • сортировать входной массив
  • выполнить один раз, сравнивая [i] с [i + 1] и удаляя дубликаты в O (N) '

Общая сложность будет равна O (N * logN), что лучше, чем предложенное вами N ^ 2.

Если вы должны сохранить первоначальный порядок, то я не готов предложить решение.

3 голосов
/ 13 января 2010

Ваш код содержит ошибки. Попробуйте запустить его с {1, 1, 1} - думаю, он вернет {1, 1}.

1 голос
/ 19 января 2010

В прошлый раз, когда я проверял, C # позволял вам сортировать 2 массива, используя один для сравнения и выполняя своп на обоих.

Вот что вы можете сделать:

  • Создать массив indices, в котором хранятся числа от 0 до N-1.
  • Сортировка array и indices с использованием array в качестве ключа.
  • Найдите дубликаты и установите индексы дубликатов в N + 1.
  • Сортировка array и indices с использованием indices в качестве ключа.
  • Измените размер массива до нужного размера и до.

Удаляет дубликаты и сохраняет порядок.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...