สร้างจำนวนสูงสุดใน C ++

สมมติว่าเรามีอาร์เรย์สองอาร์เรย์ที่มีความยาว m และ n โดยมีตัวเลข 0-9 แทนตัวเลขสองตัว เราต้องสร้างจำนวนความยาวสูงสุด k ที่น้อยกว่า m + n จากตัวเลขทั้งสอง เราต้องจำไว้ว่าต้องรักษาลำดับสัมพัทธ์ของตัวเลขจากอาร์เรย์เดียวกัน เราต้องหาอาร์เรย์ของตัวเลข k ดังนั้นหากอินพุตเป็นเช่น [3,4,7,5] และ [9,1,3,5,8,4] และ k =5 คำตอบจะเป็น [9,8,7,5,4 ].

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

• กำหนดฟังก์ชัน mergeThem() ซึ่งจะใช้อาร์เรย์ nums1 อาร์เรย์ nums2
• กำหนดอาร์เรย์ ret
• ผม :=0, j :=0, n :=ขนาดของ nums1, m :=ขนาดของ nums2
• ในขณะที่ (i
• ถ้าเรียกใช้ฟังก์ชันมากขึ้น (nums1, nums2, i, j) เป็นจริง −
  • ใส่ nums1[i] ที่ส่วนท้ายของ ret
  • (เพิ่ม i ขึ้น 1)
• มิฉะนั้น
  • แทรก nums2[j] ที่ส่วนท้ายของ ret
  • (เพิ่ม j ขึ้น 1)

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> mergeThem(vector<int> nums1, vector<int> nums2)
   {
      vector<int> ret;
      int i = 0;
      int j = 0;
      int n = nums1.size();
      int m = nums2.size();
      while (i < n || j < m) {
         if (greater(nums1, nums2, i, j)) {
            ret.push_back(nums1[i]);
            i++;
         }
         else {
            ret.push_back(nums2[j]);
            j++;
         }
      }
      return ret;
   }
   vector<int> modify(vector<int>& v, int k)
   {
      stack<int> st;
      vector<int> ret;
      for (int i = 0; i < v.size(); i++) {
         int x = v[i];
         while (!st.empty() && st.top() < x && st.size() + (v.size() - i) - 1 >= k) {
            st.pop();
         }
         if (st.size() < k)
            st.push(x);
         }
         while (!st.empty()) {
            ret.push_back(st.top());
            st.pop();
         }
         reverse(ret.begin(), ret.end());
         return ret;
      }
      bool greater(vector<int>& a, vector<int>& b, int i, int j)
      {
         while (i < a.size() && j < b.size() && a[i] == b[j])
         i++, j++;
         return j == b.size() || (i < a.size() && a[i] > b[j]);
      }
      vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k)
      {
         vector<int> ret;
         int n = nums1.size();
         int m = nums2.size();
         for (int i = 0; i <= k; i++) {
            if (i <= n && (k - i) <= m) {
               vector<int> candidate = mergeThem(modify(nums1, i), modify(nums2, k - i));
               if (greater(candidate, ret, 0, 0)) {
                  ret = candidate;
               }
            }
         }
         return ret;
     }
};
main() {
   Solution ob;
   vector<int> v = { 3, 4, 7, 5 }, v1 = { 9, 1, 3, 5, 8, 4 };
   print_vector(ob.maxNumber(v, v1, 5));
}

อินพุต

{ 3, 4, 7, 5 }
{ 9, 1, 3, 5, 8, 4 }
5

ผลลัพธ์

[9, 8, 7, 5, 4, ]