检测序列的排列

Question

我有一个像这样的数字列表(数组)

1 2 3 4

所以我的目标是给另一个数组的检查,如果这个数组,如果原来的例子的排列,阵列(3 4 1 2)和(1 2 4 3)是原始但排列(1 2 1 1)或(1 5 4 3)没有.

Answer 1

两种可能的解决方案是

(1) O(n)空间和平均时间的解决方案将是创建一个直方图,基于哈希表中,数据的-并检查直方图identicals.想法是 - 计算每个列表中每个元素出现的数量,然后检查每个元素在每个数组中出现的时间完全相同.

伪代码:

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)时间解决方案是对两个数组进行排序,然后迭代并检查它们是否相同.