- Splice the maximum number – enumerate all groups – monotonic stack + greedy algorithm
Given two arrays of length m and n respectively, their elements consist of 0-9, representing the digits in each bit of the two natural numbers. Now select k (k <= m + n) numbers from these two arrays and splice them into a new number. The numbers taken from the same array are required to maintain their relative order in the original array.
Find the maximum number that satisfies this condition. The result is an array of length k representing the maximum number.
Note: Please optimize the time and space complexity of your algorithm as much as possible.
Example 1:
enter:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k=5
Output:
[9, 8, 6, 5, 3]
Example 2:
enter:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k=5
Output:
[6, 7, 6, 0, 4]
Example 3:
enter:
nums1 = [3, 9]
nums2 = [8, 9]
k=3
Output:
[9, 8, 9]
For this question, what is the key point? For example, if we want to combine to get the largest number, then we know how to combine the two given arrays.
Assume that the first array has eight numbers
The second array has nine numbers
Now take three numbers from the first and three numbers from the second. The three numbers taken should be the largest three-digit number. This is mainly due to this inference.
After we know this inference, our goal becomes to take out all the combinations, then splice the maximum number of these combinations, and then find the largest one from these maximum numbers. The problem-solving code is as follows:
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void monotone_stack(int *nums,int count,int *s,int numsSize){<!-- -->
int top=0;
for(int i=0;i<numsSize;i + + ){<!-- -->
// printf("top %d ",top);
if(i==0){<!-- -->
s[top + + ]=nums[i];
}
else{<!-- -->
if(top>=1)
while(top>=1 & amp; & amp;nums[i]>s[top-1] & amp; & amp;numsSize-i>=count-top + 1){<!-- -->
top--;
}
if(top<count){<!-- -->
s[top + + ]=nums[i];
}
}
}
}
void print(int *nums,int numsSize){<!-- -->
for(int i=0;i<numsSize;i + + ){<!-- -->
printf("%d ",nums[i]);
}
}
void find_max(int *ret,int k,int *s1,int *s2,int n1,int n2){<!-- -->
int p1=0,p2=0;
int i=0;
for(;i<k;){<!-- -->
if(p1==n1||p2==n2){<!-- -->
break;
}
else{<!-- -->
if(s1[p1]>s2[p2]){<!-- -->
ret[i]=s1[p1];
p1 + + ;
i + + ;
}
else if(s1[p1]<s2[p2]){<!-- -->
ret[i]=s2[p2];
p2 + + ;
i + + ;
}
else if(s1[p1]==s2[p2]){<!-- -->
// ret[i]=s1[p1];
// p1 + + ;
int po1=p1;
int po2=p2;
while(s1[po1]==s2[po2]){<!-- -->
po1++;
po2++;
if(po1==n1){<!-- -->
break;
}
if(po2==n2){<!-- -->
break;
}
}
if(po1==n1){<!-- -->
ret[i]=s2[p2];
p2 + + ;
i + + ;
}
else if(po2==n2){<!-- -->
ret[i]=s1[p1];
p1 + + ;
i + + ;
}
else{<!-- -->
if(s1[po1]>s2[po2]){<!-- -->
ret[i]=s1[p1];
p1 + + ;
i + + ;
// printf(" %d i %d ",ret[i],i);
}
if(s1[po1]<s2[po2]){<!-- -->
ret[i]=s2[p2];
p2 + + ;
i + + ;
}
}
}
}
}
while(p1!=n1){<!-- -->
ret[i + + ]=s1[p1 + + ];
}
while(p2!=n2){<!-- -->
ret[i + + ]=s2[p2 + + ];
}
for(int i=0;i<k;i + + ){<!-- -->
printf("-%d ",ret[i]);
}
}
int* maxNumber(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int* returnSize){<!-- -->
int *s1=(int *)malloc(sizeof(int)*nums1Size);
int *s2=(int *)malloc(sizeof(int)*nums2Size);
int *re=(int *)malloc(sizeof(int)*k);
int *ret=(int *)malloc(sizeof(int)*k);
*returnSize=k;
int pz=0;
for(int i=1;i<=nums1Size & amp; & amp;i<=k;i + + ){<!-- -->
if(nums2Size>=k-i){<!-- -->
monotone_stack(nums1,i,s1,nums1Size);
monotone_stack(nums2,k-i,s2,nums2Size);
printf("||");
// print(s1,i);
// print(s2,k-i);
if(pz==0){<!-- -->
find_max(re,k,s1,s2, i, k-i);
pz=1;
}
else{<!-- -->
find_max(ret,k,s1,s2, i, k-i);
for(int j=0;j<k;j + + ){<!-- -->
if(ret[j]>re[j]){<!-- -->
for(int kz=0;kz<k;kz + + ){<!-- -->
re[kz]=ret[kz];
}
break;
}
if(ret[j]<re[j]){<!-- -->
break;
}
}
}
}
}
return re;
}