避免使用嵌套for循環

Question

我正在解決一個編碼挑戰，並且由於超時導致大量輸入的測試用例中我的代碼失敗。

我正在使用一個嵌套的for循環來查找關於它們的順序的整數數組中的最小差異（排序不是一個選項）。例如：這個數組中的最小差異：{20,7,8,2,5}是（7-5 = 2）不是（8-7 = 1）。

我知道使用嵌套for循環對於執行時間來說是不好的。在這種情況下，我搜索了很多替代方法來使用嵌套循環，但未能找到任何內容。

有沒有一種方法來實現這個算法，而不使用嵌套for循環？

Answer 1

高效：爲O（n log n）的

的想法是使用排序。以下是步驟。

1）按升序對數組進行排序。如果您使用合併或快速排序，此步驟需要O（n日誌n）時間。

2）將差值初始化爲無窮大。這一步需要O（1）次。

3）比較排序數組中的所有相鄰對並跟蹤最小差異。此步驟需要O（n）時間

#include <bits/stdc++.h> 
using namespace std; 


int MinDiff(int arr[], int n) 
{ 
    // Sort array in non-decreasing order 
    sort(arr, arr+n); 

    // Initialize difference as infinite 
    int diff = INT_MAX; 

    // Find the min diff by comparing adjacent 
    // pairs in sorted array 
    for (int i=0; i<n-1; i++) 
     if (arr[i+1] - arr[i] < diff) 
      diff = arr[i+1] - arr[i]; 


    return diff; 
}