552. Create Maximum Number

站起来为这道题鼓掌。是我比较喜欢的一道题,解法十分巧妙,代码可以写的很简洁,比如寻找最大子数组的时候我用的方法超级麻烦,还用了堆栈,然后再输出到数组。其实完全没必要,直接利用指针就可以漂亮的完成。

这道题没啥坑,或者说处处都是需要考虑清楚的否则别说corner case连一般的test case都不能过。其中我犯的一个错误就是,在得到两个子数组以后需要拼合成最大的一个数字,不能简单的像merge sort那样,比两个谁大谁merge,因为这里两个并不是sorted的数组,也会有duplicated。所以要持续地比下去,还有要考虑其中一个比另一个短如果其中一个没有数字了的情况。

这道题要写两个辅助函数,一个是负责将一个数组返回其长度为k的最大的子数组,然后二一个函数是比较两个数组在给定的俩index的开始谁能组成的数字更大,从而用于生成最大数字。

直接贴算法把,我觉得每一行都不是白给的,值得反复看

public class Solution {
 public int[] maxNumber(int[] nums1, int[] nums2, int k) {
 int[] ans = new int[k];
 for (int i = Math.max(k — nums2.length, 0); i <= Math.min(nums1.length, k); i++) {
 int[] res1 = get_max_sub_array(nums1, i);
 int[] res2 = get_max_sub_array(nums2, k — i);
 int[] res = new int[k];
 int pos1 = 0, pos2 = 0, tpos = 0;

while (pos1 < res1.length || pos2 < res2.length) {
 res[tpos++] = greater(res1, pos1, res2, pos2) ? res1[pos1++] : res2[pos2++];
 }

if (!greater(ans, 0, res, 0))
 ans = res;
 }

return ans;
 }

public boolean greater(int[] nums1, int start1, int[] nums2, int start2) {
 for (; start1 < nums1.length && start2 < nums2.length; start1++, start2++) {
 if (nums1[start1] > nums2[start2]) return true;
 if (nums1[start1] < nums2[start2]) return false;
 }
 return start1 != nums1.length;
 }

public int[] get_max_sub_array(int[] nums, int k) {
 int[] res = new int[k];
 int len = 0;
 for (int i = 0; i < nums.length; i++) {
 while (len > 0 && len + nums.length — i > k && res[len — 1] < nums[i]) {
 len — ;
 }
 if (len < k)
 res[len++] = nums[i];
 }
 return res;
 }
}

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.