leetcode: Merge Sorted Array

问题描述：

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 andnums2 are m and n respectively.

原问题链接：https://leetcode.com/problems/merge-sorted-array/

 

问题分析

　　这个问题相对比较简单，也比较容易找到思路。对于这两个数组来说，一个数组的实际长度可能远超过它们两个数组里有效元素个数的和。假设数组1里元素个数为m，数组２里元素个数为n，可以从数组１里的m + n -1这个位置开始，从后往前去处理。

　　我们取3个变量，分别为i, l, r。其中i表示最终在数组里当前位置所放置元素的索引，l表示数组１中间最后一个元素的位置，r表示数组２中间最后一个元素的位置。每次比较l, r的值，将大的那个放入到i的位置。在详细的实现中还需要考虑如果一个数组遍历完的情况。

　　详细的代码实现如下：

 

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i = m + n - 1, l = m - 1, r = n - 1; i >= 0; i--) {
            if(l >= 0 && r >= 0) {
                if(nums1[l] < nums2[r]) nums1[i] = nums2[r--];
                else nums1[i] = nums1[l--];    
            } else if(r < 0) return;
            else if(l < 0) nums1[i] = nums2[r--];
        }
    }
}