การเรียงสับเปลี่ยนที่แต่ละองค์ประกอบระบุจำนวนองค์ประกอบก่อนหรือหลัง?

ในส่วนนี้เราจะเห็นปัญหาหนึ่งข้อ ที่นี่ n องค์ประกอบจะได้รับในอาร์เรย์ เราต้องตรวจสอบว่ามีการเรียงสับเปลี่ยนของอาร์เรย์นั้นหรือไม่ โดยแต่ละองค์ประกอบจะระบุจำนวนองค์ประกอบที่มีอยู่ก่อนหรือหลังอาร์เรย์นั้น

สมมติว่าองค์ประกอบอาร์เรย์คือ {2, 1, 3, 3} การเรียงสับเปลี่ยนที่เหมาะสมคือ {3, 1, 2, 3} ในที่นี้ 3 ตัวแรกแสดงว่ามีองค์ประกอบอยู่ 3 ตัวถัดจากนั้น 1 หมายถึงมีองค์ประกอบเพียงตัวเดียวก่อนหน้าสิ่งนี้ 2 บ่งชี้ว่ามีองค์ประกอบอยู่ 2 ตัวก่อนหน้า และ 3 ตัวสุดท้ายบ่งชี้ว่ามีองค์ประกอบอยู่ก่อนหน้า 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