Merge Sorted Array

发表于 分类于 阅读次数：

题目链接: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 and nums2 are m and n respectively.
由题意得：
1.A和B两个数组都是有序的数组，大小分别为m和n
2.合并两数组在A数组中，A数组容量足够大。
思路分析：如果暴力解法即(无脑解法)，遍历A数组和B数组每个元素比较，若A[i] < B[j]，则继续比较下一个B元素，否则将A数组i及之后的元素往后移动以为。这种解法想想就不可能。换一种思路两数组都反向递减遍历。两数组总长度index = m+n-1, 遍历若A[i] < B[j]，则A[index] = A[j] j–,否则A[index] = B[i] i–,index–。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int[] megerArray(int[] A, int m, int[] B, int n){
    int aCount = m-1, bCount = n-1, index = m+n-1;
    while (index >= 0){
        if(aCount>=0 && bCount>=0){
            if(A[aCount] > B[bCount]){
                A[index] = A[aCount];
                aCount--;
            }else {
                A[index] = A[bCount];
                bCount--;
            }
        }else if(aCount >= 0){
            A[index] = A[aCount];
            aCount--;
        }else if(bCount >=0){
            A[index] = A[bCount];
            bCount--;
        }
        index--;
    }
    return A;
}