每个元素指示其之前或之后的元素数量的排列？
在本节中，我们将看到一个问题。在这里，n个元素在一个数组中给出。我们必须检查该数组是否存在排列，以便每个元素指示在其之前或之后存在的元素数量。
假设数组元素为{2，1，3，3}。适当的排列类似于{3，1，2，3}。这里的前3个表示紧随其后的三个元素，1表示在此之前仅一个元素。2表示之前有两个元素，后3表示之前有三个元素。
算法
checkPermutation(arr,n)
begin
define a hashmap to hold frequencies. The key and value are of integer type of the map.
for each element e in arr, do
increase map[e] by 1
done
for i := 0 to n-1, do
if map[i] is non-zero, then
decrease map[i] by 1
else if map[n-i-1] is non-zero, then
decrease map[n-i-1] by 1
else
return false
end if
done
return true
end示例
#include<iostream>
#include<map>
using namespace std;
bool checkPermutation(int arr[], int n) {
map<int, int> freq_map;
for(int i = 0; i < n; i++){ //get the frequency of each number
freq_map[arr[i]]++;
}
for(int i = 0; i < n; i++){
if(freq_map[i]){ //count number of elements before current element
freq_map[i]--;
} else if(freq_map[n-i-1]){ //count number of elements after current element
freq_map[n-i-1]--;
} else {
return false;
}
}
return true;
}
main() {
int data[] = {3, 2, 3, 1};
int n = sizeof(data)/sizeof(data[0]);
if(checkPermutation(data, n)){
cout << "Permutation is present";
} else {
cout << "Permutation is not present";
}
}输出结果
Permutation is present