阵列最大差距的计算

我正在研究这个问题，这里有详细的问题和描述。其实我找了几个解决方案，都很相似。我的问题是，为什么只计算跨桶差距？为什么不考虑桶内的最大/最小差异？谢谢。阵列最大差距的计算

给定一个未排序的数组，找出排序后的元素之间的最大差异。

尝试在线性时间/空间中解决它。

如果数组包含少于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通过你提供的算法在所有点都在同一个桶中的情况下有问题（例如，如果所有点都是相同的） –

阵列最大差距的计算

回答

相关问题