C++で最大数を作成する

---

長さmとnの2つの配列があり、0〜9の数字が2つの数値を表しているとします。 2桁の数字からm+n未満の長さkの最大数を作成する必要があります。同じ配列の数字の相対的な順序を保持する必要があることに注意する必要があります。 k桁の配列を見つける必要があります。したがって、入力が[3,4,7,5]と[9,1,3,5,8,4]のようで、k =5の場合、答えは[9,8,7,5,4]になります。 ]。

これを解決するには、次の手順に従います-

• 関数mergeThem（）を定義します。これには、配列nums1、配列nums2が必要です。
• 配列retを定義する
• i：=0、j：=0、n：=nums1のサイズ、m：=nums2のサイズ
• while（i
• 関数greater（nums1、nums2、i、j）を呼び出すと、-
  • retの最後にnums1[i]を挿入
  • （iを1増やします）
• それ以外の場合
  • retの最後にnums2[j]を挿入します
  • （jを1増やします）

return ret

関数modify（）を定義します。これには、配列v、kが必要です。

1つのスタックstを定義する

配列retを定義する

iを初期化する場合：=0、i

x：=v [i]

while（stは空ではなく、st =kのサイズ）、do −

• stから要素を削除

st

xをstに挿入

（stが空ではない）間、-

を実行します
• retの最後にstの一番上の要素を挿入します
• stから要素を削除

配列を逆にするret

return ret

関数greater（）を定義します。これには、配列a、配列b、i、j、

が必要です。

（i

iを1増やし、jを1増やします

j==bのサイズまたはib [j]

の場合、trueを返します。

メインの方法から次の手順を実行します。

配列retを定義する

n：=nums1のサイズ

m：=nums2のサイズ

iを初期化する場合：=0、i <=kの場合、更新（iを1つ増やす）、実行-

• i <=nかつ（k --i）<=mの場合、-
  • 配列候補を定義する=mergeThem（modify（nums1、i）、modify（nums2、k --i））
  • great（candidate、ret、0、0）が真の場合、-
  • ret：=候補

return ret

理解を深めるために、次の実装を見てみましょう-

例

#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, ]