2014
11-18

# LeetCode-Merge Sorted Array[排序]

### Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.

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

//LeetCode, Merge Sorted Array
// 时间复杂度O(m+n)，空间复杂度O(1)
class Solution {
public:
void merge(int A[], int m, int B[], int n) {
int ia = m - 1, ib = n - 1, icur = m + n - 1;
while(ia >= 0 && ib >= 0) {
A[icur--] = A[ia] >= B[ib] ? A[ia--] : B[ib--];
}
while(ib >= 0) {
A[icur--] = B[ib--];
}
}
};


Java代码:

public class Solution {
public void merge(int A[], int m, int B[], int n) {
int i = m-1;
int j = n-1;
int index = m+n-1;
while(i >= 0 && j >= 0){
if(A[i] > B[j])
A[index--] = A[i--];
else
A[index--] = B[j--];

}
while(i >= 0) A[index--] = A[i--];
while(j >= 0) A[index--] = B[j--];
}
}

1. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法

2. for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dp = dp [j-1] + 1;
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp = dp[i-1] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp = Math.max(dp [j - 1] + 1, dp );
}
}
这里的代码似乎有点问题？ dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false