如何将两个排序的数组合并到排序的数组？(How to merge two sorted arrays into a sorted array? [closed])

如何将两个排序的数组合并到排序的数组？(How to merge two sorted arrays into a sorted array? [closed])

这是在采访中被问到我，这是我提供的解决方案：

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; }

有没有更有效的方式来做到这一点？

编辑：校正长度方法。

This was asked of me in an interview and this is the solution I provided:

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; }

Is there a more efficient way to do this?

Edit: Corrected length methods.

最满意答案

稍微改进，但在主循环之后，当您到达另一个的末尾时，可以使用System.arraycopy复制任何一个输入数组的尾部。 这不会改变您的解决方案的O(n)性能特征。

A minor improvement, but after the main loop, you could use System.arraycopy to copy the tail of either input array when you get to the end of the other. That won't change the O(n) performance characteristics of your solution, though.