Вопрос по algorithm, arrays, language-agnostic, permutation – Обнаружить перестановку последовательности

3

У меня есть список номеров, как это (массив)

1 2 3 4

Так что моей целью является проверка заданного другого массива, если этот массив, если перестановка исходного примера, массив(3 4 1 2) а также(1 2 4 3) перестановки оригинала, но(1 2 1 1) или же(1 5 4 3) не.

Ваш Ответ

1   ответ
7

Два возможных решения:

(1) O(n) пространство & Средним временем решения будет созданиегистограммана основе хеш-таблицы данных - и проверьте, идентичны ли гистограммы. Идея состоит в том, чтобы - посчитать, сколько каждого элемента появляется в каждом списке, а затем проверить, чтобы увидеть каждый элемент появляетсяименно так одинаковые времена в каждом массиве.

псевдокод:

map1 = new map //first histogram
map2 = new map //second histogram
for each element in arr1: //create first histogram
   if (element in map1):
         map1.put(element,map1.get(element)+1)
   else:
         map1.put(element,1)
for each element in arr2: //create second histogram
   if (element in map2):
         map2.put(element,map2.get(element)+1)
   else:
         map2.put(element,1)
for each key in map 1: //check all elements in arr1 appear in arr2
   if map1.get(key) != map2.get(key):
        return false
//make sure the sizes also match, it means that each element in arr2 appears in arr1.
return arr1.length == arr2.length 

(2) O(nlogn) Временным решением будет сортировка обоих массивов, а затем итерация и проверка их идентичности.

Можете ли вы объяснить немного первый вариант? eli.rodriguez
Второй работает хорошо, есть несколько хороших алгоритмов eli.rodriguez
Ваш псевдокод гистограммы реализован на Python:from collections import Counter; return Counter(arr1) == Counter(arr2), :) Dougal
@Dougal: спасибо. Так как это был не специфичный для Python вопрос - я подумал, что было бы хорошо показать OP, как он на самом деле идет (код Python будет преобразован во что-то очень похожее на это, если я верю). Но да - это показывает нам простоту языка высокого уровня по сравнению с языками низкого уровня. amit
@ eli.rodriguez: Альтернатива - решение на основе гистограммы? Я добавил псевдокод amit

Похожие вопросы