如何將大小爲M的數組合併到另一個大小爲2M的數組中

Question

我在線上的代碼挑戰中得到了這個問題。我需要合併兩個排序的數組，其中一個大小M與M元素到另一個，M元素和容量2M。我提供了以下解決方案：

class ArraysSorting { 

/** 
* Function to move elements at the end of array 
* 
* @param bigger array 
*/ 
void moveToEnd(int bigger[]) { 
    int i = 0, j = bigger.length - 1; 
    for (i = bigger.length - 1; i >= 0; i--) 
     if (bigger[i] != 0) { 
      bigger[j] = bigger[i]; 
      j--; 
     } 
} 

/** 
* Merges array smaller array of size M into bigger array of size 2M 
* @param bigger array 
* @param smaller array 
*/ 
void merge(int bigger[], int smaller[]) { 
    moveToEnd(bigger); 
    int i = smaller.length; 
    int j = 0; 
    int k = 0; 
    while (k < (bigger.length)) { 
     if ((i < (bigger.length) && bigger[i] <= smaller[j]) || (j == smaller.length)) { 
      bigger[k] = bigger[i]; 
      k++; 
      i++; 
     } else { 
      bigger[k] = smaller[j]; 
      k++; 
      j++; 
     } 
    } 
    } 
} 

有沒有更有效的方法來做到這一點？

的時間複雜度：O(2M)

Answer 1

你不能擊敗線性時間，因爲你必須至少掃描所有2M元素，所以這是你所能得到的最好。

實際上，你可以進一步優化它。沒有必要將bigger的元素轉移到最後;只需從右到左寫結果而不是從左到右（當然，您需要反轉比較，在任何一步您都會選擇最大的元素而不是最小的元素）。

此外，這是不好：

if ((i < (bigger.length) && bigger[i] <= smaller[j]) || (j == smaller.length)) { 
    /* ... */ 
} 

你應該訪問smaller[j]之前測試j == smaller.length;代碼原樣可能會訪問smaller中的邊界位置。做到這一點，而不是：

if ((j == smaller.length) || (i < (bigger.length) && bigger[i] <= smaller[j])) { 
    /* ... */ 
} 

總體來說，我認爲你可以使代碼更簡單，這裏的東西，在我看來，因爲if條件更小，更容易理解更容易閱讀（它也接近傳統的方式其中合併兩個數組，並避免換擋元件到後面）的額外O(M)工作：

void merge(int bigger[], size_t bigger_len, int smaller[], size_t smaller_len) { 
    ssize_t smaller_i, bigger_i, idx; 

    if (smaller_len == 0) 
     return; 

    smaller_i = smaller_len-1; 

    if (bigger_len == 0) 
     bigger_i = -1; 
    else 
     bigger_i = bigger_len-1; 

    idx = bigger_len+smaller_len-1; 

    while (smaller_i >= 0 && bigger_i >= 0) { 
     if (bigger[bigger_i] > smaller[smaller_i]) { 
      bigger[idx] = bigger[bigger_i]; 
      bigger_i--; 
     } 
     else { 
      bigger[idx] = smaller[smaller_i]; 
      smaller_i--; 
     } 
     idx--; 
    } 

    while (smaller_i >= 0) { 
     bigger[idx] = smaller[smaller_i]; 
     smaller_i--; 
     idx--; 
    } 
} 

可以很容易地看出，第一環，只要在不同的陣列兩個元素之間的比較是運行可能的（而不是讓循環總是運行並使用複雜的if裏面測試）。另請注意，由於輸出正在寫入bigger，所以一旦第一個循環終止，我們只需確保剩下的smaller的其餘（如果有）複製到bigger。代碼以C語言編寫，但在Java中幾乎相同。 bigger_len和smaller_len是bigger和smaller中的元素數;假設bigger有足夠的空間用於bigger_len+smaller_len元素。對於分配給smaller_i和bigger_i的初始if測試對於處理邊界情況是必要的，其中減1將溢出（無符號）範圍size_t;在Java中它們是不必要的，因爲Java沒有無符號類型（如果我錯了，請糾正我，我最近沒有做過Java）。

時間複雜度仍然爲O(M)。