Tạo số tối đa trong C ++

Giả sử chúng ta có hai mảng độ dài m và n với các chữ số 0-9 đại diện cho hai số. Chúng ta phải tạo ra số độ dài k lớn nhất nhỏ hơn m + n từ các chữ số của hai chữ số. Chúng ta phải ghi nhớ rằng thứ tự tương đối của các chữ số trong cùng một mảng phải được giữ nguyên. Chúng ta phải tìm mảng gồm k chữ số. Vì vậy, nếu các đầu vào như [3,4,7,5] và [9,1,3,5,8,4] và k =5, thì câu trả lời sẽ là [9,8,7,5,4 ].

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

• Xác định một hàm mergeThem (), điều này sẽ nhận một mảng nums1, một mảng nums2,
• Xác định ret mảng
• i:=0, j:=0, n:=kích thước của nums1, m:=kích thước của nums2
• while (i
• nếu gọi hàm lớn hơn (nums1, nums2, i, j) là true, thì -
  • chèn nums1 [i] vào cuối ret
  • (tăng tôi lên 1)
• Mặt khác
  • chèn nums2 [j] vào cuối ret
  • (tăng j lên 1)

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

Ví dụ

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

Đầu vào

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

Đầu ra

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