Hoán đổi tối thiểu để làm cho chuỗi ngày càng tăng trong C ++

Giả sử chúng ta có hai dãy số nguyên A và B có cùng độ dài khác 0. Chúng ta có thể hoán đổi phần tử A [i] và B [i]. Chúng ta phải ghi nhớ rằng cả hai phần tử đều ở cùng một vị trí chỉ mục trong trình tự tương ứng của chúng. Sau khi hoàn thành một số giao dịch hoán đổi, A và B đều đang tăng dần lên. Chúng tôi phải tìm số lượng hoán đổi tối thiểu để làm cho cả hai chuỗi ngày càng tăng nghiêm ngặt.

Vì vậy, nếu đầu vào giống như A =[1,3,5,4] và B =[1,2,3,7], thì câu trả lời sẽ là 1, nếu chúng ta hoán đổi A [3] với B [3], thì các trình tự sẽ là A =[1,3,5,7] và B =[1,2,3,4], cả hai đều đang tăng dần.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mảng A, tạo hai mảng swapCnt và noSwapCnt có kích thước n mỗi mảng

• chèn 1 vào swapCnt và 0 vào noSwapCnt

• cho tôi trong phạm vi từ 1 đến n - 1

  • swapCnt [i]:=n và noSwapCnt:=n

  • nếu A [i]> A [i - 1] VÀ B [i]> B [i - 1], thì

    • noSwapCnt [i]:=noSwapCnt [i - 1]

    • swapCnt [i]:=swapCnt [i - 1] + 1

  • nếu A [i]> B [i - 1] và B [i]> A [i - 1], thì

    • swapCnt [i]:=tối thiểu swapCnt [i], 1 + noSwapCnt [i - 1]

    • noSwapCnt [i]:=tối thiểu swapCnt [i - 1], noSwapCnt [i]

• trả về tối thiểu swapCnt [n - 1], noSwapCnt [n - 1]

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minSwap(vector<int>& A, vector<int>& B) {
      int n = A.size();
      vector <int> swapCnt(n), noSwapCnt(n);
      swapCnt[0] = 1;
      noSwapCnt[0] = 0;
      for(int i = 1; i < n; i++){
         swapCnt[i] = n;
         noSwapCnt[i] = n;
         if(A[i] > A[i - 1] && B[i] > B[i - 1]){
            noSwapCnt[i] = noSwapCnt[i - 1];
            swapCnt[i] = swapCnt[i - 1] + 1;
         }
         if(A[i] > B[i - 1] && B[i] > A[i - 1]){
            swapCnt[i] = min(swapCnt[i], 1 + noSwapCnt[i - 1]);
            noSwapCnt[i] = min(swapCnt[i - 1], noSwapCnt[i]);
         }
      }
      return min(swapCnt[n - 1], noSwapCnt[n - 1]);
   }
};
main(){
   vector<int> v1 = {1,3,5,4};
   vector<int> v2 = {1,2,3,7};
   Solution ob;
   cout << (ob.minSwap(v1, v2));
}

Đầu vào

[1,3,5,4]
[1,2,3,7]

Đầu ra

1