Leetcode - Merge Sorted Array

Paste_Image.png

My code:

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (nums1 == null || nums1.length == 0)
            return;
        if (nums2 == null || nums2.length == 0)
            return;
        
        if (m == 0 && n != 0) {
            for (int j = 0; j < n; j++)
                nums1[j] = nums2[j];
            return;
        }
        else if (m != 0 && n == 0)
            return;
        else if (m == 0 && n == 0)
            return;
        
        int s1 = 0;
        int s2 = 0;
        while (s1 < m && s2 < n) {
            if (nums1[s1] <= nums2[s2]) {
                s1++;
            }
            else {
                for (int j = m; j > s1; j--)
                    nums1[j] = nums1[j - 1];
                nums1[s1++] = nums2[s2++];
                m++;
            }
        }
        if (s1 >= m) {
            for (int j = s2; j < n; j++)
                nums1[s1++] = nums2[j];
        }
    }
    
    public static void main (String[] args) {
        Solution test = new Solution();
        int[] nums1 = {1, 0};
        int[] nums2 = {2};
        test.merge(nums1, 1, nums2, 1);
    }
}

My test result:

这次题目比较简单。但还是有些细节需要考虑到,即 m 是需要变的,不是定值。
当 nums1[s1] <= nums2[s2] 时, s1++,然后继续比较。
如果 .... > .... 时,就需要将s1之后的数组元素都整体向后移动一格,并且s2++,同时,一定会遗漏的一点是,m++,这样才能保证数组动态性,并且与逻辑一致。
这道题目提示是 two pointers, but I think it should be "three pointers"

**
总结: Array, three pointers
**

Anyway, Good luck, Richardo!

My code:

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0)
            return;
        if (m < 0 || n < 0)
            return;
        int[] sortedArr = new int[m + n];
        int i = 0; // index of nums1
        int j = 0; // index of nums2
        for (int k = 0; k < m + n; k++) {
            if (i >= m)
                sortedArr[k] = nums2[j++];
            else if (j >= n)
                sortedArr[k] = nums1[i++];
            else if (nums1[i] < nums2[j])
                sortedArr[k] = nums1[i++];
            else
                sortedArr[k] = nums2[j++];
        }
        for (i = 0; i < m + n; i++)
            nums1[i] = sortedArr[i];
    }
}

用一个循环就可以把问题解决,不需要再分类讨论了。

Anyway, Good luck, Richardo!

My code:

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        while (i >= 0 || j >= 0) {
            if (i < 0) {
                nums1[k--] = nums2[j--];
            }
            else if (j < 0) {
                nums1[k--] = nums1[i--];
            }
            else if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            }
            else {
                nums1[k--] = nums2[j--];
            }
        }
    }
}

reference:
https://discuss.leetcode.com/topic/2461/this-is-my-ac-code-may-help-you/2

可以不用申请额外内存。从后往前扫描。

Anyway, Good luck, Richardo! -- 09/25/2016

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容