Detect a permutation of sequence

问题:

I have a list of numbers like this (array)

1 2 3 4

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.

回答1:

Two possible solutions are:

(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.

pseudo 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) time solution will be to sort both arrays, and then iterate and check if they are identical.

回答2:

If you definitely have a sequence you may check if a given array is its permutation much faster. Just calculate a sum of all element of your sequence and compare it with a sum of elements in the given array.

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;
}