leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0321.cpp (1319B)

      1 class Solution {
      2     static bool greater(const vector<int> &nums1, const vector<int> &nums2, int i, int j) {
      3         while (i < size(nums1) && j < size(nums2) && nums1[i] == nums2[j])
      4             i++, j++;
      5         return j == size(nums2) || (i < size(nums1) && nums1[i] > nums2[j]);
      6     }
      7 
      8     static vector<int> merge(const vector<int> &nums1, const vector<int> &nums2, int k) {
      9         vector<int> res(k);
     10 
     11         for (int i = 0, j = 0, l = 0; l < k; l++) {
     12             res[l] = greater(nums1, nums2, i, j) ? nums1[i++] : nums2[j++];
     13         }
     14 
     15         return res;
     16     }
     17 
     18     static vector<int> maxArr(const vector<int> &nums, int k) {
     19         const int n = size(nums);
     20         vector<int> res(k);
     21 
     22         for (int i = 0, j = 0; i < n; i++) {
     23             while (n - i + j > k && j > 0 && res[j - 1] < nums[i])
     24                 j--;
     25             if (j < k) res[j++] = nums[i];
     26         }
     27 
     28         return res;
     29     }
     30 
     31   public:
     32     vector<int> maxNumber(const vector<int> &nums1, const vector<int> &nums2, int k) const {
     33         const int n = size(nums1), m = size(nums2);
     34         vector<int> res(k);
     35 
     36         for (int i = max(0, k - m); i <= k && i <= n; i++) {
     37             const auto candid = merge(maxArr(nums1, i), maxArr(nums2, k - i), k);
     38             res = max(res, candid);
     39         }
     40 
     41         return res;
     42     }
     43 };