如何將兩個排序數組合并為排序數組？這是我在一次面試中被問到的，這就是我提供的解決方案：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;}有更有效的方法嗎？編輯：修正長度方法。
3 回答
Qyouu
TA貢獻1786條經驗 獲得超11個贊
public static int[] merge(int[] a, int[] b) {
int[] answer = new int[a.length + b.length];
int i = a.length - 1, j = b.length - 1, k = answer.length;
while (k > 0)
answer[--k] =
(j < 0 || (i >= 0 && a[i] >= b[j])) ? a[i--] : b[j--];
return answer;}利益點
請注意，它所執行的操作數量與任何其他操作相同或更少。 O(N)
算法，但在字面上單語句在一個時間循環！ 如果兩個數組的大小大致相同，則O(N)的常數是相同的。但是，如果數組確實不平衡，則使用 System.arraycopy會贏，因為在內部，它可以使用單個x86程序集指令來完成這一任務。 通知 a[i] >= b[j]而不是 a[i] > b[j]..這保證了“穩定性”，即當a和b的元素相等時，我們希望a中的元素位于b之前。
森林海
TA貢獻2011條經驗 獲得超2個贊
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;}添加回答
舉報
0/150
提交
取消