如何将两个有序数组合并成一个有序数组？
如何将两个有序数组合并成一个有序数组？
提问于 2011-05-11 09:13:58
这是我在一次采访中被问到的，这是我提供的解决方案：
public static int[] merge(int[] a, int[] b) {
int[] answer = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
{
if (a[i] < b[j])
{
answer[k] = a[i];
i++;
}
else
{
answer[k] = b[j];
j++;
}
k++;
}
while (i < a.length)
{
answer[k] = a[i];
i++;
k++;
}
while (j < b.length)
{
answer[k] = b[j];
j++;
k++;
}
return answer;
}有没有更有效的方法来做到这一点？
编辑:更正的长度方法。
回答 27
Stack Overflow用户
回答已采纳
发布于 2011-05-11 09:19:50
这是一个小的改进，但是在主循环之后，当您到达另一个输入数组的末尾时，可以使用System.arraycopy来复制另一个输入数组的尾部。不过，这不会改变解决方案的O(n)性能特征。
Stack Overflow用户
发布于 2012-01-21 07:59:25
public static int[] merge(int[] a, int[] b) {
int[] answer = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
answer[k++] = a[i] < b[j] ? a[i++] : b[j++];
while (i < a.length)
answer[k++] = a[i++];
while (j < b.length)
answer[k++] = b[j++];
return answer;
}是更紧凑一点，但完全相同！
Stack Overflow用户
发布于 2011-05-11 09:18:36
任何可以改进的地方都是微优化，整个算法是正确的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5958169
复制相关文章
相似问题