检测序列的排列

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)空间和平均时间的解决方案是根据哈希表创建数据的histogram-并检查直方图是否相同。想法是-计算每个元素在每个列表中出现的数量，然后检查每个元素在每个数组中完全出现的次数相同。

伪代码：

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

Answer 2

如果您确实有序列，则可以检查给定数组的排列是否快得多。只需计算序列中所有元素的总和，然后将其与给定数组中的元素总和进行比较即可。

bool is_permutation(vector<int> &v, vector<int> &s) {
    // size of the sequence
    int v_size = v.size();
    // size of probable permutation.
    int s_size = s.size();
    // Calculate a sum of all elements of the sequence
    int sum_of_sequence = (v_size * (1 + v_size)) / 2;
    // Count actual sum of elements
    int sum_of_all_elements = std::accumulate(v.begin(), v.end(), 0);
    // If the sums are equal the array contains a permuted sequence
    return sum_of_sequence == sum_of_all_elements;
}