home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Swap ขั้นต่ำเพื่อสร้างลำดับที่เพิ่มขึ้นใน C++

สมมติว่าเรามีลำดับจำนวนเต็ม A และ B สองลำดับที่มีความยาวไม่เป็นศูนย์เหมือนกัน เราสามารถสลับองค์ประกอบ A[i] และ B[i] เราต้องจำไว้ว่าองค์ประกอบทั้งสองอยู่ในตำแหน่งดัชนีเดียวกันในลำดับตามลำดับ หลังจากเสร็จสิ้นการสลับจำนวนหนึ่งแล้ว A และ B ก็เพิ่มขึ้นอย่างเคร่งครัด เราต้องหาจำนวนการแลกเปลี่ยนขั้นต่ำเพื่อให้ทั้งสองลำดับเพิ่มขึ้นอย่างเคร่งครัด

ดังนั้นหากอินพุตเป็นเหมือน A =[1,3,5,4] และ B =[1,2,3,7] คำตอบจะเป็น 1 หากเราสลับ A[3] กับ B[3] จากนั้นลำดับจะเป็น A =[1,3,5,7] และ B =[1,2,3,4] ทั้งคู่กำลังเพิ่มขึ้นอย่างเคร่งครัด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • n :=ขนาดของอาร์เรย์ สร้างสองอาร์เรย์ swapCnt และ noSwapCnt ของขนาด n แต่ละรายการ

  • แทรก 1 ลงใน swapCnt และ 0 ลงใน noSwapCnt

  • สำหรับฉันอยู่ในช่วง 1 ถึง n – 1

    • swapCnt[i] :=n และ noSwapCnt :=n

    • ถ้า A[i]> A[i – 1] และ B[i]> B[i – 1] แล้ว

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

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

    • ถ้า A[i]> B[i – 1] และ B[i]> A[i – 1] แล้ว

      • swapCnt[i] :=ขั้นต่ำของ swapCnt[i], 1 + noSwapCnt[i – 1]

      • noSwapCnt[i] :=ขั้นต่ำของ swapCnt[i – 1], noSwapCnt[i]

  • คืนค่าขั้นต่ำของ swapCnt[n – 1], noSwapCnt[n – 1]

ตัวอย่าง(C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −

#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));
}

อินพุต

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

ผลลัพธ์

1