陣列最大差距的計算

我正在研究這個問題，這裏有詳細的問題和描述。其實我找了幾個解決方案，都很相似。我的問題是，爲什麼只計算跨桶差距？爲什麼不考慮桶內的最大/最小差異？謝謝。陣列最大差距的計算

給定一個未排序的數組，找出排序後的元素之間的最大差異。

嘗試在線性時間/空間中解決它。

如果數組包含少於2個元素，則返回0。

您可能會認爲數組中的所有元素都是非負整數，並且符合32位有符號整數範圍。

int maximumGap(vector<int>& nums) { 
     const int n = nums.size(); 
     if(n<=1) return 0; 
     int maxE = *max_element(nums.begin(),nums.end()); 
     int minE = *min_element(nums.begin(),nums.end()); 
     double len = double(maxE-minE)/double(n-1); 
     vector<int> maxA(n,INT_MIN); 
     vector<int> minA(n,INT_MAX); 
     for(int i=0; i<n; i++) { 
      int index = (nums[i]-minE)/len; 
      maxA[index] = max(maxA[index],nums[i]); 
      minA[index] = min(minA[index],nums[i]); 
     } 
     int gap = 0, prev = maxA[0]; 
     for(int i=1; i<n; i++) { 
      if(minA[i]==INT_MAX) continue; 
      gap = max(gap,minA[i]-prev); 
      prev = maxA[i]; 
     } 
     return gap; 
}

來源

2015-10-20 Lin Ma

你有n個元素，你想把它們放在給定的時間間隔內。假設區間長度爲L.G的可能值是多少？兩個連續元素之間的最大差距？顯然G不可能超過L，G也不能小於L/n-1。 G將爲等於至L/n-1當且僅當我們將所有元素精確地分開（即所有元素距彼此相等的距離）。

，因爲現在這條規則，如果你創建一個大小的水桶精確L/n-1我們有兩個選擇 - 所有的元素彼此相等的距離，因此答案是L/n-1，或者答案是比L/n-1更大。如果答案大於L/n-1，則不可能找到同一個存儲桶中的兩個元素（因爲每個存儲桶的長度爲L/n-1），這就是爲什麼我們只考慮存儲桶之間的距離。

爲避免考慮兩種情況，我通常會在左端關閉桶並在右端打開桶。也就是說，最左邊的點包含在桶中，最右邊的點包含在下一個桶中。最後一個桶由單個點組成 - 間隔的結束。

來源

2015-10-20 07:31:21

謝謝Ivaylo，我的困惑是，假設元素均勻分佈在所有桶中，那麼我們也應該考慮maxA [index] - minA [index]呢？如果是這樣，爲什麼解決方案不計入這種情況？謝謝。 –

@LinMa我正要爲此添加一個句子。 –

@LinMa通過你提供的算法在所有點都在同一個桶中的情況下有問題（例如，如果所有點都是相同的） –

陣列最大差距的計算

回答

相關問題