[LC 321]. 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. You should try to optimize your time and space complexity.

以下是在discussion中最好理解的也最clean的一种做法:

总体思路:每个array先组成最大的数字,然后在merge。第一个array先组成i位的数字,第二个再组成k-i位的,当试过所有的组合之后,就可以找到最大值。

细节实现:
1.对单个array找最大值,用stack。例如[9,1,5,8,3], 找到3位的最大值:准备一个stack,push 9,push 1,5比stack最上面的1大,而且array还剩3个元素,所以pop 1,push 5,8比5大,array还剩2个元素,所以pop 5,push 8,最后push 3.

2.merge的时候用两个pointer,指到两个array分别找到的最大值,谁指的数字比较大,当前的结果就取大的。当两个pointer指到的数字相等时,值得注意,需要看后面的数字谁比较大才能决定结果的当前位应该取哪个数字。例如combine [1,9]和[1,8,4],i和j分别指向第一个6和第二个6,结果先取哪个6需要看后面的数字哪个大。因为9比8大,最后得到19184。如果在第一步中随便取一个6,取到了第二个,就变成了18419.

    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] res = new int[k];
        for (int i = Math.max(0, k - len2); i <= Math.min(k, len1); i++) {
            int[] n1 = maxArray(nums1, i);
            int[] n2 = maxArray(nums2, k - i);
            int[] n = merge(n1, n2, k);
            if (greater(n, 0, res, 0)) res = n;
        }

        return res;
    }

    private int[] merge(int[] a, int[] b, int k) {
        int[] ans = new int[k];
        for (int i = 0, j = 0, r = 0; r < k; r++) {
            ans[r] = greater(a, i, b, j) ? a[i++] : b[j++];
        }
        return ans;
    }

    private boolean greater(int[] a, int i, int[] b, int j) {
        while (i < a.length && j < b.length && a[i] == b[j]) {
            i++;
            j++;
        }
        return j == b.length || (i < a.length && a[i] > b[j]);
    }

    private int[] maxArray(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[k];
        for (int i = 0, j = 0; i < n; i++) { // i for nums, j for ans while (n - i + j > k && j > 0 && nums[i] > ans[j - 1]) j--; // mimic a stack pop
            if (j < k) ans[j++] = nums[i]; // mimic a stack push
        }
        return ans;
    }

有几点需要注意
1.第5行,i从max(0, k-len2)开始。i代表需要从array1构建的max number的位数,需要从0开始,一直算到k的情况,这样array2就从k位一直构建到0位。但是有一种情况array1不能从0位开始,只能构建k-len2位,这种情况是k=len1+len2,刚好两个array的长度加一起就是k,那两个array都不能去掉任何数字,最后结果就是直接把两个array merge到一起。从数学的角度,i需要满足
i <= k
i <= len1
k – i <= len2 => i >= k – len2
i >= 0

2.第23行greater这个function,第一次没想到要写这个,然后在主function里重复使用。是失败后才觉得这样写比较concise的。

3.第35行(应该缩紧,wordpress的格式不知道怎么回事就是调不好)while的条件:新遇到的数字如果大于stack最上面的数字,而且array剩下的数字还够的话,就要pop stack最上面的数字,然后再push新数字。计算是否array剩下的数字还够:i和n是数字array的指针和总长度,j是结果数组的指针和总长度,所以当n – i <= k – j的时候,无论如何不能再pop了,所以pop的条件是n – i + j > k.

4.time complexity: for 循环中call了两个maxArray,都是O(m+n), 但merge在worst case是O((m+n)^2),即如果merge两个数组总是遇到相同的数字,到最后一位才能分出大小,就需要每一位上check剩余所有数字。另,for loop的循环次数i最大取到k,k即是m+n,所以总体time complexity是O((m+n)^3)。分析过程中发现,如果把merge的复杂度降下来,会有很大帮助。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s