在O（N * log（N））時間比較兩個不同大小的int數組？

Question

我需要比較兩個不同大小的int數組。

它必須是最高效的。

是否可以在O（N * log（N））時間內做？

它應該打印兩個數組之間不同的整數。

Answer 1

算法是O（n），但您假定數組大小相同，每個數組的大小爲ARY_SIZE。

我不會爲你解決整個作業，但是我建議你從下面的函數頭開始：int compar2arr(int arrA[], int arrA_size, int arrB[], int arrB_size)。

請記住，對於函數參數int arrA[]僅等價於int* arrA。如基思和塞巴斯蒂安所指出的，arrA_size != arrB_size意味着不同（除非任務的作者以其他方式定義它）。所以你在開始時檢查並返回false如果它成立。

編輯

好吧，我重新看了你的帖子，似乎你只是需要顯示所有不等於元素，你不知道如何處理這樣的事實，他們是不同的尺寸。

因此，我建議先從以下內容：

int compar2arr(int arrA[], int arrA_size, int arrB[], int arrB_size) 
{ 
    int smaller_size = // arrA_size or arrB size, the smaller one; 
    int higher_size = // arrA_size or arrB size, the higher one; 
    int *bigger_array; 
    int i;  
    int result = true; 

    if (arrA_size > arrB_size) 
     bigger_array = arrA; 
    else 
     bigger_array = arrB; 

    for (i = 0; i < smaller_size; i++) 
    { 
     if (/* i-th elements are not(!!) equal */) 
     { 
     result = false; 
     // print the values to be different 
     } 
    } 

    if (smaller_size != higher_size) 
    result = false; 

    for (i = smaller_size; i < higher_size; i++) 
    { 
     // print bigger_array[i] 
    } 

    return result; 
} 

我相信你能拿出實際的代碼替換註釋。 這不是最簡潔的書寫方式，而是想讓它易於理解。無論如何，計算複雜度是O（n），儘可能好。

Answer 2

如果兩個數組的大小不同，則它們已經不同，不需要比較內容，只是大小。

Answer 3

如果您只需要打印不同的元素，則在0（n）時間內不可能。解決問題的最好方法是對兩個數組進行排序（使用qsort），然後從零循環到兩個數組大小中較小的一個。

此外，如果您嘗試打印所有不匹配的整數，則在達到第一個不同的整數時無法中斷。你想要做的是在每次找到不匹配的元素時打印出「％d在％d處與％d不匹配」或類似的東西。

最後，如果大小不相等，我會遍歷較長數組的最後一部分並打印出額外的元素。