问题描述
我有一个数字是这样的(阵列)名单
I have a list of numbers like this (array)
1 2 3 4
所以我的目标是给另一个数组,如果检查这个数组,如果原来的例子的置换,数组(3 4 1 2)
和(1 2 4 3)
是原来的,但(1 2 1 1)
或(1 5 4排列3)
不是。
So my goal is the check given another array if this array if a permutation of the original example, the array (3 4 1 2)
and (1 2 4 3)
are permutations of the original but (1 2 1 1)
or (1 5 4 3)
not.
推荐答案
两个可能的解决方案是:
Two possible solutions are:
(1) O(N)
空间和放大器;数据的平均时间的解决方案是创建一个直方图,基于哈希表, - 和检查直方图identicals。我们的想法是 - 算多少的每个元素出现在每一个列表中,然后检查每一个元素出现的完全的每个数组中相同的时间
(1) O(n)
space & average time solution will be to create a histogram, based on a hash table, of the data - and check if the histograms are identicals. The idea is - count how many each element appears in each list, and then check to see each element appears exactly the same times in each array.
伪code:
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)
时间解决方法是将两个数组排序,然后遍历,并检查它们是相同的。
(2) O(nlogn)
time solution will be to sort both arrays, and then iterate and check if they are identical.
这篇关于检测序列的置换的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!