首頁猿問如何將兩個排序數(shù)組合并為排序數(shù)組？

如何將兩個排序數(shù)組合并為排序數(shù)組？

Java 算法算法與數(shù)據(jù)結(jié)構(gòu)

一只名叫tom的貓 2019-07-09 18:11:42

如何將兩個排序數(shù)組合并為排序數(shù)組？這是我在一次面試中被問到的，這就是我提供的解決方案：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貢獻(xiàn)1786條經(jīng)驗(yàn) 獲得超11個贊

我感到驚訝的是，沒有人提到這種更酷、更高效、更緊湊的實(shí)現(xiàn)：

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

利益點(diǎn)

請注意，它所執(zhí)行的操作數(shù)量與任何其他操作相同或更少。
O(N)
算法，但在字面上單語句在一個時間循環(huán)！
如果兩個數(shù)組的大小大致相同，則O(N)的常數(shù)是相同的。但是，如果數(shù)組確實(shí)不平衡，則使用
System.arraycopy
會贏，因?yàn)樵趦?nèi)部，它可以使用單個x86程序集指令來完成這一任務(wù)。
通知
a[i] >= b[j]
而不是
a[i] > b[j]
..這保證了“穩(wěn)定性”，即當(dāng)a和b的元素相等時，我們希望a中的元素位于b之前。

1 反對回復(fù) 2019-07-09

森林海

TA貢獻(xiàn)2011條經(jīng)驗(yàn) 獲得超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;}

是有點(diǎn)緊湊，但完全一樣！

反對回復(fù) 2019-07-09