给定一个数组，求其排序形式中两个连续元素之间的最大差值。 例如：
null
Input: arr[] = {1, 10, 5}Output: 5Sorted array would be {1, 5, 10} andmaximum adjacent difference would be 10 - 5 = 5Input: arr[] = {2, 4, 8, 11}Output: 4
天真的解决方案：
首先对数组进行排序，然后遍历它，并跟踪相邻元素之间的最大差异。 该方法的时间复杂度为O（nlogn）。
高效的解决方案： 这 解决方案 是基于 鸽子洞分拣 。无需对数组进行排序，只需填充桶并跟踪每个桶的最大值和最小值。如果发现一个空桶，最大间隙为 中的最大值 上一个桶–桶中的最小值 下一桶 .
因为我们想对这些进行分类，这样我们就可以有最大的差距。同样对于任何第i个元素，（arr[i]-min_值）/（max_值-min_值）的值随着arr[i]的增加而不断增加，并且该值始终在0到1之间变化。当我们想把排序后的结果放入大小为n的桶中时，我们将这个值乘以（n-1），从而生成一个变量 增量=（最大值–最小值）/（n-1） .现在在maxBucket或minBucket中，在索引any i之前的任何索引j处的所有值将始终小于索引i处的值，对于j （arr[i]-最小值）/delta 因此，我们制作了两种不同的桶maxBucket和minBucket。
正如我们所发现的 连续值 我们必须考虑到当前索引的最大可能值为PurvayValm和当前索引i的MimBuff[i]，ANS将是ANS和MimBuff[I] -PurvayValax的最大值。
让我们用这种方法来解决上面的例子。
工作示例：
输入 ：arr[]={1,10,5}
产出：5
第一步 ：查找最大值和最小值
最大值=10，最小值=1
步骤二 ：计算增量
增量=（最大值–最小值）/（n-1）
增量=（10-1）/（3-1）=4.5
步骤三 ：初始化bucket，maxBucket={INT_MIN}，minBucket={INT_MAX}
步骤四 ：对于任何索引i，在bucket中计算索引arr[i]并在bucket中更新，
in=（arr[i]-min_val）/delta
maxBucket[in]=max（maxBucket[in]，arr[i]）
minBucket[in]=min（minBucket[in]，arr[i]）
对于arr中的所有索引，值为=>0,2,0
maxBucket=[5，INT_MIN，10]
minBucket=[1，INT_MAX，10]
第五步 ：因此ans是minBucket[i]的最大值（上一个索引的最大值）
在这种情况下，对于i=2:max_gap=max（max_gap，minBucket[2]–max（maxBucket[1]，maxBucket[0]））
最大间隙=10-5=5
这只是为了展示这个概念，所有其他的基本验证都在主代码中。
以下是上述方法的代码：
C++
// CPP program to find maximum adjacent difference // between two adjacent after sorting. #include <bits/stdc++.h> using namespace std; int maxSortedAdjacentDiff( int * arr, int n) { // Find maximum and minimum in arr[] int maxVal = arr[0], minVal = arr[0]; for ( int i = 1; i < n; i++) { maxVal = max(maxVal, arr[i]); minVal = min(minVal, arr[i]); } // Arrays to store maximum and minimum values // in n-1 buckets of differences. int maxBucket[n - 1]; int minBucket[n - 1]; fill_n(maxBucket, n - 1, INT_MIN); fill_n(minBucket, n - 1, INT_MAX); // Expected gap for every bucket. float delta = ( float )(maxVal - minVal) / ( float )(n - 1); // Traversing through array elements and // filling in appropriate bucket if bucket // is empty. Else updating bucket values. for ( int i = 0; i < n; i++) { if (arr[i] == maxVal || arr[i] == minVal) continue ; // Finding index of bucket. int index = ( float )( floor (arr[i] - minVal) / delta); maxBucket[index] = max(maxBucket[index], arr[i]); minBucket[index] = min(minBucket[index], arr[i]); } // Finding maximum difference between maximum value // of previous bucket minus minimum of current bucket. int prev_val = minVal; int max_gap = 0; for ( int i = 0; i < n - 1; i++) { if (minBucket[i] == INT_MAX) continue ; max_gap = max(max_gap, minBucket[i] - prev_val); prev_val = maxBucket[i]; } max_gap = max(max_gap, maxVal - prev_val); return max_gap; } int main() { int arr[] = { 1, 10, 5 }; int n = sizeof (arr) / sizeof (arr[0]); cout << maxSortedAdjacentDiff(arr, n) << endl; return 0; } |
JAVA
// Java program for the above approach import java.util.Arrays; // Java program to find maximum adjacent difference // between two adjacent after sorting. class GFG { static int maxSortedAdjacentDiff( int [] arr, int n) { // Find maximum and minimum in arr[] int maxVal = arr[ 0 ]; int minVal = arr[ 0 ]; for ( int i = 1 ; i < n; i++) { maxVal = Math.max(maxVal, arr[i]); minVal = Math.min(minVal, arr[i]); } // Arrays to store maximum and minimum values // in n-1 buckets of differences. int maxBucket[] = new int [n - 1 ]; int minBucket[] = new int [n - 1 ]; Arrays.fill(maxBucket, 0 , n - 1 , Integer.MIN_VALUE); Arrays.fill(minBucket, 0 , n - 1 , Integer.MAX_VALUE); // Expected gap for every bucket. float delta = ( float )(maxVal - minVal) / ( float )(n - 1 ); // Traversing through array elements and // filling in appropriate bucket if bucket // is empty. Else updating bucket values. for ( int i = 0 ; i < n; i++) { if (arr[i] == maxVal || arr[i] == minVal) { continue ; } // Finding index of bucket. int index = ( int )(Math.round((arr[i] - minVal) / delta)); // Filling/Updating maximum value of bucket if (maxBucket[index] == Integer.MIN_VALUE) { maxBucket[index] = arr[i]; } else { maxBucket[index] = Math.max(maxBucket[index], arr[i]); } // Filling/Updating minimum value of bucket if (minBucket[index] == Integer.MAX_VALUE) { minBucket[index] = arr[i]; } else { minBucket[index] = Math.min(minBucket[index], arr[i]); } } // Finding maximum difference between maximum value // of previous bucket minus minimum of current // bucket. int prev_val = minVal; int max_gap = 0 ; for ( int i = 0 ; i < n - 1 ; i++) { if (minBucket[i] == Integer.MAX_VALUE) { continue ; } max_gap = Math.max(max_gap, minBucket[i] - prev_val); prev_val = maxBucket[i]; } max_gap = Math.max(max_gap, maxVal - prev_val); return max_gap; } // Driver program to run the case public static void main(String[] args) { int arr[] = { 1 , 10 , 5 }; int n = arr.length; System.out.println(maxSortedAdjacentDiff(arr, n)); } } |
Python3
# Python3 program to find maximum adjacent # difference between two adjacent after sorting. def maxSortedAdjacentDiff(arr, n): # Find maximum and minimum in arr[] maxVal, minVal = arr[ 0 ], arr[ 0 ] for i in range ( 1 , n): maxVal = max (maxVal, arr[i]) minVal = min (minVal, arr[i]) # Arrays to store maximum and minimum # values in n-1 buckets of differences. maxBucket = [INT_MIN] * (n - 1 ) minBucket = [INT_MAX] * (n - 1 ) # Expected gap for every bucket. delta = (maxVal - minVal) / / (n - 1 ) # Traversing through array elements and # filling in appropriate bucket if bucket # is empty. Else updating bucket values. for i in range ( 0 , n): if arr[i] = = maxVal or arr[i] = = minVal: continue # Finding index of bucket. index = (arr[i] - minVal) / / delta # Filling/Updating maximum value # of bucket if maxBucket[index] = = INT_MIN: maxBucket[index] = arr[i] else : maxBucket[index] = max (maxBucket[index], arr[i]) # Filling/Updating minimum value of bucket if minBucket[index] = = INT_MAX: minBucket[index] = arr[i] else : minBucket[index] = min (minBucket[index], arr[i]) # Finding maximum difference between # maximum value of previous bucket # minus minimum of current bucket. prev_val, max_gap = minVal, 0 for i in range ( 0 , n - 1 ): if minBucket[i] = = INT_MAX: continue max_gap = max (max_gap, minBucket[i] - prev_val) prev_val = maxBucket[i] max_gap = max (max_gap, maxVal - prev_val) return max_gap # Driver Code if __name__ = = "__main__" : arr = [ 1 , 10 , 5 ] n = len (arr) INT_MIN, INT_MAX = float ( '-inf' ), float ( 'inf' ) print (maxSortedAdjacentDiff(arr, n)) # This code is contributed by Rituraj Jain |
C#
// C# program to find maximum // adjacent difference between // two adjacent after sorting. using System; using System.Linq; class GFG { static int maxSortedAdjacentDiff( int [] arr, int n) { // Find maximum and minimum in arr[] int maxVal = arr[0]; int minVal = arr[0]; for ( int i = 1; i < n; i++) { maxVal = Math.Max(maxVal, arr[i]); minVal = Math.Min(minVal, arr[i]); } // Arrays to store maximum and // minimum values in n-1 buckets // of differences. int []maxBucket = new int [n - 1]; int []minBucket = new int [n - 1]; maxBucket = maxBucket.Select(i => int .MinValue).ToArray(); minBucket = minBucket.Select(i => int .MaxValue).ToArray(); // maxBucket.Fill(int.MinValue); // Arrays.fill(minBucket, 0, n - 1, Integer.MAX_VALUE); // Expected gap for every bucket. float delta = ( float ) (maxVal - minVal) / ( float ) (n - 1); // Traversing through array elements and // filling in appropriate bucket if bucket // is empty. Else updating bucket values. for ( int i = 0; i < n; i++) { if (arr[i] == maxVal || arr[i] == minVal) { continue ; } // Finding index of bucket. int index = ( int ) (Math.Round((arr[i] - minVal) / delta)); // Filling/Updating maximum value of bucket if (maxBucket[index] == int .MinValue) { maxBucket[index] = arr[i]; } else { maxBucket[index] = Math.Max(maxBucket[index], arr[i]); } // Filling/Updating minimum value of bucket if (minBucket[index] == int .MaxValue) { minBucket[index] = arr[i]; } else { minBucket[index] = Math.Min(minBucket[index], arr[i]); } } // Finding maximum difference between // maximum value of previous bucket // minus minimum of current bucket. int prev_val = minVal; int max_gap = 0; for ( int i = 0; i < n - 1; i++) { if (minBucket[i] == int .MaxValue) { continue ; } max_gap = Math.Max(max_gap, minBucket[i] - prev_val); prev_val = maxBucket[i]; } max_gap = Math.Max(max_gap, maxVal - prev_val); return max_gap; } // Driver Code public static void Main() { int []arr = {1, 10, 5}; int n = arr.Length; Console.Write(maxSortedAdjacentDiff(arr, n)); } } // This code contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to find maximum adjacent difference // between two adjacent after sorting. function maxSortedAdjacentDiff(arr, n) { // Find maximum and minimum in arr[] var maxVal = arr[0], minVal = arr[0]; for ( var i = 1; i < n; i++) { maxVal = Math.max(maxVal, arr[i]); minVal = Math.min(minVal, arr[i]); } // Arrays to store maximum and minimum values // in n-1 buckets of differences. var maxBucket = Array(n-1).fill(-1000000000); var minBucket = Array(n-1).fill(1000000000); // Expected gap for every bucket. var delta = (maxVal - minVal) / (n - 1); // Traversing through array elements and // filling in appropriate bucket if bucket // is empty. Else updating bucket values. for ( var i = 0; i < n; i++) { if (arr[i] == maxVal || arr[i] == minVal) continue ; // Finding index of bucket. var index = Math.floor((arr[i] - minVal) / delta); maxBucket[index] = Math.max(maxBucket[index], arr[i]); minBucket[index] = Math.min(minBucket[index], arr[i]); } // Finding maximum difference between maximum value // of previous bucket minus minimum of current bucket. var prev_val = minVal; var max_gap = 0; for ( var i = 0; i < n - 1; i++) { if (minBucket[i] == 1000000000) continue ; max_gap = Math.max(max_gap, minBucket[i] - prev_val); prev_val = maxBucket[i]; } max_gap = Math.max(max_gap, maxVal - prev_val); return max_gap; } var arr = [1, 10, 5]; var n = arr.length; document.write( maxSortedAdjacentDiff(arr, n)); </script> |
输出
5
时间复杂性： O（n） 辅助空间： O（n）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
