数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学一种排列，其中每个元素都表示它前面或后面的元素个数？
在本节中，我们将看到一个问题。这里给定一个数组中的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
更新于：2019年7月30日
70 次浏览
广告