Small gray part recall part tell about at that time the scene of interview……
If I have an unordered array of integers, how can I find the maximum difference between any two adjacent elements of this array? The time and space complexity should be as low as possible. (for example: unordered array 2,3,1,4,6, sorted by 1,2,3,4,6, maximum difference is 6-4=2)
Solution a:
Use a fast stable sorting algorithm (such as merge algorithm, N*logN) to sort the original array, and then iterate over the sorted array, taking the difference of every two adjacent elements and finally getting the maximum difference.
The time complexity of this solution is O (N*logN), and the space complexity is O (N) without changing the original array.
Method 2:
1. Using the idea of counting sort, the interval length k (k= max-min +1) of the maximum value and minimum value Min of the original array is firstly calculated.
2. Create a new Array Array whose length is K.
3. Iterate over the original Array and insert each element of the original Array into the corresponding position of the new Array. For example, if the value of the element is n, insert the element into Array[n-min]. Part of the Array is empty and part of the Array is filled with values.
4. Iterate through Array and count the maximum number of consecutive null values in Array +1, which is the maximum difference between adjacent elements.
For example, given an unordered array {2, 6, 3, 4, 5, 10, 9}, the processing process is shown as follows:
The time complexity of the solution is O (n+k), and the space complexity is also O (n+k).
Method 3:
1. Using the idea of bucket sorting, find the unit interval length d of the original array from Min to Max, d=(max-min)/n. The function of d is to determine the interval range division of each barrel.
2. Create an Array whose length is N+1. Each element of the Array is a List representing a bucket.
3. Iterate over the original Array and insert each element of the original Array into the bucket corresponding to the new Array. The conditions for entering each bucket are based on different value intervals (see the figure below for details). Since the total number of buckets is N+1, at least one bucket is empty.
4. Iterate through the new Array Array and calculate the difference between the minimum value in the right non-empty bucket and the maximum value in the left non-empty bucket. The maximum value difference is the maximum difference between the adjacent non-empty bucket after sorting the original Array.
For example, given an unordered array {0, 6, 3, 16, 7, 10, 9, 11, 20, 18}, the processing process is shown as follows:
The time complexity of this solution is O (n), and the space complexity is also O (n).
Ten minutes later……
The above is the small gray interview……
— — the END — — –
If you like this article, please long click the picture below to follow the subscription number programmer Xiao Grey and watch more exciting content
