Questions about the merge() function

  • 0

    Here I am talking about the most common merge() function appearing in the posted solutions. Actually, I am not quite convinced about the way to handle the cases where we have two equal elements. I know, intuitively, we should move forward the pointer of the array that has a larger element after passing through the equal part, as this makes the larger element more likely to be encountered sooner, thus appear in a more significant digit. But can anyone post a rigorous mathematical proof of this?

    private int[] merge(int[] nums1, int[] nums2) {
                int[] merged = new int[ nums1.length+nums2.length ];
                int cnt, cnt1, cnt2;
                for(cnt = cnt1 = cnt2 = 0; cnt1<nums1.length && cnt2<nums2.length; ) {
                    merged[ cnt++ ] = greater(nums1, nums2, cnt1, cnt2)?nums1[ cnt1++ ]:nums2[ cnt2++ ];
                for(; cnt1 < nums1.length; merged[ cnt++ ] = nums1[ cnt1++ ]);
                for(; cnt2 < nums2.length; merged[ cnt++ ] = nums2[ cnt2++ ]);
                return merged;
            private boolean greater(int[] nums1, int[] nums2, int start1, 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;

Log in to reply

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