首页 > 代码库 > [LeetCode]88 Merge Sorted Array
[LeetCode]88 Merge Sorted Array
https://oj.leetcode.com/problems/merge-sorted-array/
http://blog.csdn.net/linhuanmars/article/details/19712333
public class Solution {
public void merge(int A[], int m, int B[], int n) {
// Solution A:
// merge_NoExtraSpace(A, m, B, n);
// Solution B:
merge_ExtraSpace(A, m, B, n);
}
/////////////////////////////
// Solution A: NoExtraSpace
//
private void merge_NoExtraSpace(int A[], int m, int B[], int n)
{
// To not using extra space. copy existing A[0,m] to A[n, m+n]
// Need to copy backwards
for (int i = m - 1 ; i >= 0 ; i --)
{
A[i + n] = A[i];
}
int i = n;
int j = 0;
int k = 0;
while (i < m + n || j < n)
{
int a = i < m + n ? A[i] : Integer.MAX_VALUE;
int b = j < n ? B[j] : Integer.MAX_VALUE;
if (a < b)
{
A[k] = a;
i ++;
}
else
{
A[k] = b;
j ++;
}
k++;
}
}
/////////////////////////////
// Solution B: ExtraSpace
//
private void merge_ExtraSpace(int A[], int m, int B[], int n)
{
int[] result = new int[m + n];
int i = 0;
int j = 0;
int k = 0;
while (i < m || j < n)
{
if (i == m)
result[k ++] = B[j ++];
else if (j == n)
result[k ++] = A[i ++];
else if (A[i] < B[j])
result[k ++] = A[i ++];
else
result[k ++] = B[j ++];
}
// Copy result to A
for (i = 0 ; i < result.length ; i ++)
{
A[i] = result[i];
}
}
}[LeetCode]88 Merge Sorted Array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。