用java解决拼接最大数问题

Question

拼接最大数
给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

说明: 请尽可能地优化你算法的时间和空间复杂度。

示例 1:

输入:
nums1 =
[3, 4, 6, 5]

nums2 =
[9, 1, 2, 5, 8, 3]

k =
5

输出:
[9, 8, 6, 5, 3]
示例 2:

输入:
nums1 =
[6, 7]

nums2 =
[6, 0, 4]

k =
5

输出:
[6, 7, 6, 0, 4]
示例 3:

输入:
nums1 =
[3, 9]

nums2 =
[8, 9]

k =
3

输出:
[9, 8, 9]

Answer 1

提供一种思路，不一定很好。
先思考单一数列中按顺序取若干元素的最大值问题。
这个问题的一种固定解法就是：在可以选择的范围内，选择最大的元素；如果有多个最大元素，选择最靠左的那个。
举例，在2868734952中选择5个数字构成最大值。
首先，第一个元素只能在最左边的"286873"中选出（因为再向右选的话剩余元素就凑不出4个数字了，也就是最后的结果凑不出5位数）。
在"286873"中最大元素是8，我们选择尽可能靠左的“8”输出，然后剩下的序列变成"68734952"
下一个元素只能在"68734"中选出，选8，剩下序列"734952"
第3个元素只能在"7349"中选出，选9，剩下序列"52"
依次类推。
最后结果是88952。

双数列要复杂的多，但是可以用类似的思路来处理它们。

假设有数列A(1,n)={a1, a2, ... an}和B(1,m)={b1,b2,...,bm}，从中要选取K个元素。怎么做呢？
显然，第1个元素要么从A(1,n)中给出，要么从B(1,m)中给出。
所以，我们可以构造数列(A(1,n),B(1,m))={a1,a2,...,an,b1,b2,...bm}，从允许的范围内挑出最靠左边的最大元素f1（这个时候挑出的元素是A中的可能性大）。
我们再构造一个数列(B(1,m),A(1,n))={b1,b2,...,bm,a1,a2,...an}，从允许的范围内挑出最靠左边的最大元素f2（这个时候挑出的元素是B中的可能性大）。
如果f1<>f2，选择大的值输出，然后把A或B中该值以及左边的内容切除；
如果f1=f2，且f1、f2都是A或都是B中的元素，则f1和f2必是同一个元素，把该元素输出，并在对应的数列中切除f1以及左边的所有元素;
如果f1=f2，但是f1是ai, f2是bj，则当前步骤无法判断哪个值更合适，需要依次递归进行后续的切割后方能判断。

大致的核心伪代码如下（偷懒起见，用char数组代表数列，用String代表输出的子序列）：

char[] A=....;
char[[ B=....;
int getMaxIndexInA(int ai, int bj, int L) {
//在{ai, ai+1,... an, bj, bj+1, ... bm}中，排除最右边的L-1个元素后，找最左边最大的元素，如果该元素属于A，返回其序号，否则返回-1。
}
int getMaxIndexInB(int ai, int bj, int L) {
//在{bj, bj+1, ... bm,ai, ai+1,... an}中，排除最右边的L-1个元素后，找最左边最大的元素，如果该元素属于B，返回其序号，否则返回-1。
}

//获取由序列{ai,...an}以及{bj,...,bm}之中的顺序最大子序列，返回其值。
String getSubList(int ai, int bi, int L) throws Exception{
if (L<=0) {
return "";
}
int next_A_index = getMaxIndexInA(ai, bj, L);
int next_B_index = getMaxIndexInB(ai, bj, L);
if ((next_A_index<0) && (next_B_index<0)) {
throw new Exception("找不到解");
}
if (next_A_index<0) {
String result = b[next_B_index];
result += getSubList(ai, next_B_index+1, L-1);
} else if (next_B_index<0) {
String result = a[next_A_index];
result += getSubList(next_A_index+1, bj, L-1);
} else {
String resultA = a[next_A_index];
resultA += getSubList(next_A_index+1, bj, L-1);
String resultB = b[next_B_index];
resultB += getSubList(ai, next_B_index+1, bj, L-1);
if (resutA<resultB) {
return resultB;
} else {
return resultA;
}
}

}

main () {
...
getSubList(0, 0, L);
...
}