資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告