12ms Java code beat 100% JavaSubmissions. A little long and messy but fast.


  • 0
    Y

    With help from other posters who explained this question so well, I finally got it.

    public class Solution {
        public int[] maxNumber(int[] nums1, int[] nums2, int k) {
            int[][] v1 = new int[k + 1][];
            int[][] v2 = new int[k + 1][];
            int k1 = Math.min(k, nums1.length);
            int k2 = Math.min(k, nums2.length);
            v1[k1] = bestPick(nums1, k1);
            v2[k2] = bestPick(nums2, k2);
            if (nums1.length + nums2.length > k) {
                for (int i = k1; i > 0; i--) v1[i - 1] = trim(v1[i], i);
                for (int i = k2; i > 0; i--) v2[i - 1] = trim(v2[i], i);
            }
            int[] merged = null;
            for (int i = 0; i <= k; i++) {
                if (v1[i] == null || v2[k - i] == null) continue;
                merged = merge(v1[i], i, v2[k - i], k - i, merged);
            }
            return merged;
        }
        
        int[] merge(int[] in1, int len1, int[] in2, int len2, int[] prev) {
            int[] merged = new int[len1 + len2];
            int i1 = 0, i2 = 0, cur = 0;
            while (i1 < len1 && i2 < len2) {
                if (in1[i1] > in2[i2]) merged[cur++] = in1[i1++];
                else if (in1[i1] < in2[i2]) merged[cur++] = in2[i2++];
                else {
                    int ii1 = i1, ii2 = i2;
                    while (in1[ii1] == in2[ii2]) {
                        if (ii1 < len1 - 1) ii1++;
                        if (ii2 < len2 - 1) ii2++;
                        if (ii1 == len1 - 1 && ii2 == len2 - 1) break;
                    }
                    if (in1[ii1] > in2[ii2]) merged[cur++] = in1[i1++];
                    else if (in2[ii2] > in1[ii1]) merged[cur++] = in2[i2++];
                    else merged[cur++] = in2[i2++];
                }
                if (prev != null) {
                    if (merged[cur - 1] < prev[cur - 1]) return prev;
                    if (merged[cur - 1] > prev[cur - 1]) prev = null;
                }
            }
            if (i1 == len1) {
                while (i2 < len2) {
                    merged[cur++] = in2[i2++];
                    if (prev != null) {
                        if (merged[cur - 1] < prev[cur - 1]) return prev;
                        if (merged[cur - 1] > prev[cur - 1]) prev = null;
                    }
                }
            } else {
                while (i1 < len1) {
                    merged[cur++] = in1[i1++];
                    if (prev != null) {
                        if (merged[cur - 1] < prev[cur - 1]) return prev;
                        if (merged[cur - 1] > prev[cur - 1]) prev = null;
                    }
                }
            }
            return merged;
        }
        
        int[] trim(int[] in, int k) {
            if (k == 1) return new int[0];
            int[] out = new int[k - 1];
            int j = 0;
            for (int i = 0; i < k; i++) {
                if (i == j && (i == k - 1 || in[i] < in[i + 1])) continue;
                out[j++] = in[i];
            }
            return out;
        }
        
        int[] bestPick(int[] in, int k) {
            if (k == 0) return new int[0];
            int[] stack = new int[Math.max(k, in.length)];
            int cur = 1;
            stack[0] = in[0];
            for (int i = 1; i < in.length; i++) {
                while (cur > 0 && in[i] > stack[cur - 1] && in.length - i > k - cur) cur--;
                stack[cur++] = in[i];
            }
            return stack;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.