arrays - シーケンスの順列を検出する

Question

このような数字のリストがあります（配列）

1 2 3 4

(3 4 1 2)したがって、私の目標は、この配列が元の例の順列である場合に別の配列を指定した場合、その配列が元の例の順列であるかどうかをチェックする(1 2 4 3)こと(1 2 1 1)です(1 5 4 3)。

Answer 1

考えられる解決策は次の 2 つです。

（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)時間の解決策は、両方の配列を並べ替えてから、それらが同一であるかどうかを繰り返して確認することです。