Questions about the merge() function


  • 0
    F

    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.