Tạo số lớn nhất trong C++

Cho 2 mảng chữ số nums1, nums2 (thứ tự chữ số trong mỗi mảng phải giữ nguyên). Tạo số lớn nhất độ dài k từ chữ số của 2 mảng.

Ví dụ

nums1 = [3,4,7,5], nums2 = [9,1,3,5,8,4], k = 5

Kết quả: [9,8,7,5,4].

Thuật toán

1. Chọn i chữ số từ nums1, k-i từ nums2 (duyệt i = 0..k).
2. Tối ưu chọn từ 1 mảng: Dùng stack đơn điệu — giữ stack giảm dần, pop khi thấy số lớn hơn và còn đủ số để đạt độ dài k.
3. Trộn 2 mảng đã chọn: So sánh lexicographically từ đầu, lấy số lớn hơn (nếu bằng nhau, so sánh tiếp).
4. Chọn kết quả lớn nhất trong tất cả i.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> 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, j = 0, n = nums1.size(), m = nums2.size();
        while (i < n || j < m) {
            if (greater(nums1, nums2, i, j)) ret.push_back(nums1[i++]);
            else ret.push_back(nums2[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(), 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;
    }
};

int main() {
    Solution ob;
    vector<int> v = {3, 4, 7, 5}, v1 = {9, 1, 3, 5, 8, 4};
    print_vector(ob.maxNumber(v, v1, 5));
    return 0;
}

Độ phức tạp

• Thời gian: O(k * (m + n)) — duyệt k lần, mỗi lần chọn + trộn O(m+n).
• Không gian: O(m + n).

Input / Output

Input:  {3,4,7,5} {9,1,3,5,8,4} 5
Output: [9, 8, 7, 5, 4]