Số điểm cố định tối đa sử dụng nhiều nhất 1 điểm hoán đổi trong C ++

Tuyên bố vấn đề

Cho một hoán vị của N phần tử từ 0 đến N-1. Điểm cố định là một chỉ mục mà tại đó giá trị giống với chỉ số, tức là arr [i] =i. Bạn chỉ được phép thực hiện nhiều nhất 1 lần hoán đổi. Tìm số điểm cố định tối đa mà bạn có thể nhận được.

Ví dụ

Nếu mảng đầu vào là {0, 1, 2, 3, 4, 6, 5} thì câu trả lời là 7.

• Để điều chỉnh điểm cố định, chúng ta phải hoán đổi 6 và 5
• Sau khi toàn bộ mảng này trở thành điểm cố định và giá trị lớn nhất của điểm cố định là 7.

Thuật toán

• Tạo một vị trí mảng giữ vị trí của từng phần tử trong mảng đầu vào
• Bây giờ, chúng tôi duyệt qua mảng và gặp các trường hợp sau -
  • Nếu, a [i] =i. Chúng tôi chỉ cần tăng số lượng và tiếp tục
  • Nếu, pos [i] =a [i] có nghĩa là hoán đổi 2 số hạng sẽ làm cho i và a [i] có điểm cố định, do đó sẽ tăng tổng số lên 2. Hãy nhớ rằng hoán đổi có thể được thực hiện nhiều nhất một lần .
• Vào cuối quá trình truyền tải, nếu chúng tôi chưa thực hiện bất kỳ hoán đổi nào, điều đó có nghĩa là hoán đổi của chúng tôi không thể tăng số lượng lên 2, vì vậy bây giờ nếu có ít nhất 2 phần tử không phải là điểm cố định, chúng tôi có thể hoán đổi để tăng số lượng lên 1, tức là biến một trong những điểm đó thành điểm cố định.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int getMaximumFixedPoints(int arr[], int n) {
   int i, pos[n], count = 0, swapped = 0;
   for (i = 0; i < n; i++)
   pos[arr[i]] = i;
   for (i = 0; i < n; i++) {
      if (arr[i] == i) {
         count++;
      } else if (swapped == 0 && pos[i] == arr[i]) {
         count += 2;
         swapped = 1;
      }
   }
   if (swapped == 0 && count < n - 1) {
      count++;
   }
   return count;
}
int main() {
   int arr[] = {0, 1, 2, 3, 4, 6, 5};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Maximum value of fixed point = " << getMaximumFixedPoints(arr, n) << endl;
   return 0;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Maximum edges = 7