算法设计与分析-Week14

发表于 | 更新于

Create Maximum Number

题目描述

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits.

Note: You should try to optimize your time and space complexity.

Example 1:

Input:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
Output: [9, 8, 6, 5, 3]

Example 2:

Input:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
Output: [6, 7, 6, 0, 4]

Example 3:

Input:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
Output: [9, 8, 9]

解题思路

本题给定了两个数组和一个整数k，要在两个数组中，一共选出k个数，使得组成的数字最大，且选出的数字相对顺序不能变化。
思路： 对于两个数组我们不是很方便直接计算，而如果在一个数组中选m个数，使得组成的数字最大，那就好做很多，因此我们只需要在一个数组中选m个数，在另一个数组中选k-m个数，最后将两组选出的数合并起来，即可得到我们想要的解。那么接下来的问题就分解为以下几个问题：

  1. 如何从一个数组中选m个数，使得组成的数字最大。对于一个给定长度的数字来说，其高位决定了它的大小，因此我们应该尽可能让这个数的高位更大。假如数组长度为n，给定整数为m，起始位置为k，那么在下标为k到n-m中找一个最大的数作为最高位，并记录该最高位的下标赋值给k，重复以上过程不断找到次高位，即可得到想要的数。
  2. 如何合并两个数组，使得结果最大。与上面的思路类似，同样是尽量使得组成的数字的高位更大，因此我写了一个greater的函数，用来判断两个数组的第一个不一样的数的大小关系。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> ans(k, 0);
        int n = nums1.size();
        int m = nums2.size();
        for(int i = max(k - m, 0); i <= k && i <= n; i++) {
            vector<int> cur = merge(maxArray(nums1, i), maxArray(nums2, k - i), k);
            if(greater(cur, 0, ans, 0)) {
                ans = cur;
            }
        }
        return ans;
    }
    
    vector<int> maxArray(vector<int> nums, int k) {
        int n = nums.size();
        if(k == n) {
            return nums;
        }
        vector<int> res(k, 0);
        int cur = 0;
        int j = 0;
        int pre = 0;
        while(k > 0) {
            int i = n - k;
            while(i >= pre) {
                if(res[cur] <= nums[i]) {
                    res[cur] = nums[i];
                    j = i + 1;
                }
                i--;
            }
            cur++;
            k--;
            pre = j;
        }
        return res;
    }
    
    vector<int> merge(vector<int> nums1, vector<int> nums2, int k) {
        vector<int> ans(k);
        for (int i = 0, j = 0, r = 0; r < k; ++r)
            ans[r] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
        return ans;
    }
    
    bool greater(vector<int> nums1, int i, vector<int> nums2, int j) {
        while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) {
            i++;
            j++;
        }
        return j == nums2.size() || (i < nums1.size() && nums1[i] > nums2[j]);
    }
};
0%