原题链接

如果把其中一个数组去掉,就是上道题去掉k位数字,获得最小数字的另一个描述.将上道题的top>a[i]改成top<a[i]即可.

但这道题有两个数组,两个数组总共需要去掉k位数,使得这k位数最大.

我的错解思路是将两个数组都排进一个数组里,但这样解不出来,并且排序很难排序.完全没有想过枚举(还以为有巧解....)

修正思路是将k位数在两数组枚举,范围在max(0,k-nums2.size())~min(k,nums1.size())只考虑nums1的范围即可,因为nums2可以用k减去

本题坑点：

 

1. 我们比较数组时,如果位数相同,需要比较下一位再看先加入哪一个,如果有个指针到达边界,我们就加入还未到边界的(即加入比较大的一个)
2. 这道题不用容器存储下标,储存原来的元素反而简单点

自己的垃圾代码：

 1 class Solution {
 2 public:
 3     vector<int> choose(int x,vector<int>& v){
 4         stack<int> stk,sk; vector<int> n1;
 5         for(int i=0;i<v.size();i++){
 6             while(!stk.empty()&&v[stk.top()]<v[i]){
 7                 n1.pop_back();
 8                 sk.push(stk.top());
 9                 stk.pop();
10             }
11             stk.push(i);
12             n1.push_back(i);
13         }
14         while(n1.size()>x)  n1.pop_back();
15         while(n1.size()<x){
16             n1.push_back(sk.top());
17             sk.pop();
18         }
19         return n1;
20     }
21     vector<int> cmp(vector<int>& v1,vector<int>& v2){
22         if(v1.size()>v2.size()) return v1;
23         else if(v1.size()<v2.size()) return v2;
24         else{
25             for(int i=0;i<v1.size();i++){
26                 if(v1[i]>v2[i]) return v1;
27                 else if(v1[i]<v2[i]) return v2;
28             }
29             return v1;
30         }
31     }
32     vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
33         vector<int> need1,need2,ans,res;
34         for(int i=max(0,k-(int)nums2.size());i<=min(k,(int)nums1.size());i++){
35             ans.clear();
36             need1 = choose(i,nums1);
37             need2 = choose(k-i,nums2);
38             sort(need1.begin(),need1.end());
39             sort(need2.begin(),need2.end());
40             int j = 0,s = 0;
41             while(j<need1.size()&&s<need2.size()){
42                 if(nums1[need1[j]]>nums2[need2[s]]){
43                     ans.push_back(nums1[need1[j]]);
44                     j++;
45                 }else if(nums1[need1[j]]==nums2[need2[s]]){
46                     int t = j; int q = s;
47                     while(t<need1.size()&&q<need2.size()&&nums1[need1[t]]==nums2[need2[q]]){
48                         q++;t++;
49                     }
50                     if(q==need2.size()){
51                         ans.push_back(nums1[need1[j]]);
52                         j++;
53                     }
54                     else if(t==need1.size()){
55                         ans.push_back(nums2[need2[s]]);
56                         s++;
57                     }
58                     else if(nums1[need1[t]]>nums2[need2[q]]) {ans.push_back(nums1[need1[j]]); j++;  }
59                     else if(nums1[need1[t]]<nums2[need2[q]]) {ans.push_back(nums2[need2[s]]); s++; }
60                 }
61                 else{
62                     ans.push_back(nums2[need2[s]]);
63                     s++;
64                 }
65             }
66             while(j<need1.size()) {
67                 ans.push_back(nums1[need1[j]]);
68                 j++;
69             }
70             while(s<need2.size()) {
71                 ans.push_back(nums2[need2[s]]);
72                 s++;
73             }
74             res = cmp(res,ans);
75         }
76         return res;
77     }
78 };

 

边界情况真心坑...