Java segment tree 3ms, unprecented 100%, O(klogn) + O(n) for best case
Basic idea is pick the maximum from nums1 and nums2, in a way that will ensure enough numbers for later picks. Two points cur1 and cur2 is maintained to ensure 
Basic idea is pick the maximum from `nums1` and `nums2`, in a way that will ensure enough numbers for later picks. Two points `cur1` and `cur2` is maintained to ensure relative orders of picks.\n\nTo make picking a maximum *O(logn)*, segment tree is used, which stores indices and the query function, `reducer`, is max function.\n\n```java\nclass Solution {\n    public int[] maxNumber(int[] nums1, int[] nums2, int k) {\n        SegmentTreeMax st1 = new SegmentTreeMax(nums1), st2 = new SegmentTreeMax(nums2);\n        int[] maxN = new int[k];\n        int cur1 = 0, cur2 = 0, remained = nums1.length + nums2.length - k;\n        for (int i = 0; i != k; ++i) {\n            int to1 = remained - cur2 + i,\n                to2 = remained - cur1 + i;\n            int picked1 = st1.reduceClosedGuarded(cur1, to1);\n            int picked2 = st2.reduceClosedGuarded(cur2, to2);\n            int comparePicked = compareIdx(nums1, picked1, nums2, picked2);\n            if (comparePicked == 0) {\n                int p1 = picked1, p2 = picked2;\n                for (int j = 1; comparePicked == 0; ++j) {\n                    p1 = st1.reduceClosedGuarded(p1 + 1, to1 + j);\n                    p2 = st2.reduceClosedGuarded(p2 + 1, to2 + j);\n                    comparePicked = compareIdx(nums1, p1, nums2, p2);\n                }\n                if (p1 == -1 && p2 == -1) {\n                    comparePicked = 0;\n                    p1 = picked1; p2 = picked2;\n                    while (comparePicked == 0) {\n                        p1 = st1.reduceClosedGuarded(cur1, p1 - 1);\n                        p2 = st2.reduceClosedGuarded(cur2, p2 - 1);\n                        comparePicked = -compareIdx(nums1, p1, nums2, p2);\n                    }\n                }\n            }\n            if (comparePicked == 1) {\n                maxN[i] = nums1[picked1];\n                cur1 = picked1 + 1;\n            }\n            else {\n                assert comparePicked == -1;\n                maxN[i] = nums2[picked2];\n                cur2 = picked2 + 1;\n            }\n        }\n        return maxN;\n    }\n    private int compareIdx(int[] nums1, int i, int[] nums2, int j) {\n        if (i == -1) return -1;\n        if (j == -1) return 1;\n        return Integer.compare(nums1[i], nums2[j]);\n    }\n}\n\nclass SegmentTreeMax {\n    private final int[] data;\n    private final int[] origin;\n    public SegmentTreeMax(int[] origin) {\n        data = new int[origin.length << 1];\n        this.origin = origin;\n        for (int i = origin.length; i != data.length; ++i) data[i] = i - origin.length;\n        for (int i = origin.length - 1; i > 0; --i) data[i] = reducer4Build(data[i << 1], data[(i << 1) | 1]);\n    }\n    private int reducer4Build(int a, int b) {\n        return (origin[a] < origin[b]) ? b : a;\n    }\n    private int reducer(int a, int b) {\n        if (a > b) {\n            a = a ^ b;\n            b = a ^ b;\n            a = a ^ b;\n        }\n        return (origin[a] < origin[b]) ? b : a;\n    }\n    public int reduceClosedGuarded(int from, int to) {\n        to = Math.min(to, origin.length - 1);\n        if (from > to) return -1;\n        int maxima = from;\n        for (int i = from + origin.length, j = to + origin.length; i <= j; i >>= 1, j >>= 1) {\n            if ((i & 1) == 1) maxima = reducer(maxima, data[i++]);\n            if ((j & 1) == 0) maxima = reducer(maxima, data[j--]);\n        }\n        return maxima;\n    }\n}\n```
[]