Проверьте, соответствуют ли два списка чисел

Учитывая два списка A, B цифр. Есть ли лучший способ проверить, равны ли они, чем решение O (N^2).Проверьте, соответствуют ли два списка чисел

источник

2012-07-04 algo_freek

Определите «равный». Тот же порядок? Дублирующие элементы? – SLaks

Вы имеете в виду «есть ли лучший способ проверить, содержат ли они одни и те же номера?» В моем списке книг равенство требует, чтобы числа были одинаковыми и в том же порядке, который, как мне кажется, требует проверки O (n). –

Любые особые характеристики списков? Они отсортированы? Ограничены ли числа? Кроме того, разрешено ли вам использовать непостоянное количество дополнительной памяти? – Jon

Если вы имеете в виду, что оба списка содержат одни и те же номера, не по отношению к упорядоченности, вы можете использовать следующий O(n *log n) алгоритм:

Сортировать обоих списках таким же образом (например, по возрастанию)
Сравнить результирующие списки по элементам, начиная с

Шаг (1) принимает 2 * O(n *log n) = O(n *log n) раз. Второй шаг выполняется в линейном O(n) времени.

Таким образом, работающий выше алгоритм решает вашу проблему в O(n *log n) времени.

источник

2012-07-04 14:23:50 Sirko

Если числа целые, вы можете использовать алгоритм сортировки по байтам, который имеет временную сложность O (n) (точнее, временная сложность O (n + r), где r - диапазон чисел), уменьшая проблему до O (n) + O (n) + O (n) = O (n) сложность –

Или двоичная сортировка радикса для 'O (n * log (r))', причем 'r' на этот раз является максимальным представимым значением, а чем фактическое максимальное значение. Это можно сделать на месте, что приятно. –

Предполагая, что числа отсортированы в списке, и оба списка имеют одинаковую длину:

bool eq = true; 

for (int i = 0; i < list1.length; i++) { 
    if (list1[i] != list2[i]) { 
     eq = false; 
     last; 
    } 
}

источник

2012-07-04 14:24:04 Ruel

Сначала проверьте, если они имеют одинаковую длину. Если они есть, вы можете поместить числа A в HashSet. Перейдите через B и проверьте, есть ли он в HashSet. Если он есть, вы можете удалить его из HashSet. Если в конце HashSet пусто, они равны. Это O (n)

Фактически дубликаты не допускаются в HashSet, поэтому вы можете иметь HashMap с ключом в качестве числа и значения как счетчика. Алгоритм остается прежним. Каждый раз, когда число B встречается в счетчике сокращения HashMap. Если в конце HashMap пуст, они равны. Это также O (n).

источник

2012-07-04 14:24:36 user1168577

Спасибо. Я тоже понял O (n * logn) algo, но мне нравились урс !! –

Спасибо. Мне тоже это нравится :). И это поможет, если вы сможете принять (опять же, только если вам понравилось :)) мой ответ, особенно потому, что (на удивление) никто не поддержал мой :). – user1168577

Отсортировать 2 перечислены O (NlogN)
Затем идут по обоим из них одновременно и видеть, что они содержат одни и те же числа О (п)

Итого: O (NlogN)

источник

2012-07-04 14:24:44

Проверьте, соответствуют ли два списка чисел

ответ

Смежные вопросы