資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++中的最大間隔
假設我們有一個未排序的陣列。我們需要找到其排序形式中連續元素之間的最大差值。如果陣列包含少於2個元素，我們將返回0。所以如果陣列是[12,3,9,1,17]，那麼輸出將是6，因為排序後的陣列將是[1,3,9,12,17]，所以3和9之間的差值6是最大差值。
為了解決這個問題，我們將遵循以下步驟：
minVal := ∞, maxCal := -∞
n := nums的大小
如果 n < 2，則返回 0;
對於 i 從 0 到 n – 1 −
minVal := nums[i] 和 minVal 的最小值
maxVal := nums[i] 和 maxVal 的最大值
gap := 向上取整 (maxVal – minVal) / (n – 1)
建立一個大小為 n – 1 的名為 bucketMax 的陣列，並用 -∞ 填充它
建立一個大小為 n – 1 的名為 bucketMin 的陣列，並用 ∞ 填充它
對於 i 從 0 到 n – 1 −
x := nums[i]
如果 x = minVal 或 x = maxVal，則跳過下一部分，進行下一次迭代
idx := (nums[i] – minVal) / gap。
bucketMax[idx] := bucketMax[idx] 和 nums[i] 的最大值
bucketMin[idx] := bucketMin[idx] 和 nums[i] 的最小值
ret := 0
prev := minVal
對於 i 從 0 到 n – 1
如果 bucketMax[i] = -∞ 且 bucketMin[i] = ∞，則跳過下一部分，進行下一次迭代
ret := ret 和 bucketMin[i] – prev 的最大值
prev := bucketMax[i]
返回 ret 和 maxVal - prev 的最大值
示例
讓我們看看下面的實現來更好地理解：
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int maximumGap(vector<int>& nums) {
lli minVal = INT_MAX;
lli maxVal = INT_MIN;
int n = nums.size();
if(n < 2) return 0;
for(int i = 0; i < n; i++){
minVal = min((lli)nums[i], minVal);
maxVal = max((lli)nums[i], maxVal);
}
int gap = ceil((double)(maxVal - minVal) / (double)(n - 1));
vector <int> bucketMax(n - 1, INT_MIN);
vector <int> bucketMin(n - 1, INT_MAX);
for(int i = 0; i < n; i++){
int x = nums[i];
if(x == minVal || x == maxVal) continue;
int idx = (nums[i] - minVal) / gap;
bucketMax[idx] = max(bucketMax[idx], nums[i]);
bucketMin[idx] = min(bucketMin[idx], nums[i]);
}
lli ret = 0;
lli prev = minVal;
for(int i = 0; i < n - 1; i++){
if(bucketMax[i] == INT_MIN && bucketMin[i] == INT_MAX) continue;
ret = max(ret, bucketMin[i] - prev);
prev = bucketMax[i];
}
return max(ret, maxVal - prev);
}
};
main(){
Solution ob;
vector<int> v = {12,3,9,1,17};
cout << (ob.maximumGap(v));
}輸入
[12,3,9,1,17]
輸出
6
327 次檢視
