An array of "maximum difference" algorithm that works in O (n)?

Question

Given an array of N integers, sort the array and find 2 consecutive numbers in the sorted array with the maximum difference.

An example is at input [1,7,3,2] output 4 (sorted array [1,2,3,7] , and the maximum difference is 7-3 = 4).

Algorithm A runs in O(NlogN) time.

I need to find an algorithm identical in function to algorithm A, which runs in O (N) time.

Answer 1

Let the array be X and let n = length (X). Put each element x in the bucket number gender ((x - min (X)) * (n - 1) / (max (X) - min (X))). The width of each bucket is (max (X) - min (X)) / (n - 1), and the maximum adjacent difference is at least the same, so the numbers in question end up in different buckets. Now all we need to do is consider the pairs in which one is maximum in bucket i and the other is min in bucket j, where i <j and all buckets k in (i, j) are empty. This is linear time.

Proof that we really need a word: let f (X) be a function. If we could calculate f (X) in linear time, then of course we could solve in linear time that

0 <f (X)? (max (X) - min (X)) / (length (X) - 1),

i, that is, whether the elements of X are uniformly distributed and not all are the same. Let this predicate be P (X). P support has factorial (length (X)) components, so regular and Omega are used; (n log n) lower bounds for algebraic computation models.

Answer 2

Perform a counting sort, and then scan the result for the biggest difference.

Due to the consistent quantity requirement, at first glance it seems that any solution will require sorting, and this at best means O (n log n) if your range of numbers is not limited enough for countable sorting. But if so, you win with O (n).

Answer 3

• Find the minimum and maximum
• Choose random number k from array
• Sort the algorithm by placing all values ​​less than k left and more than k to the right.
• You know the minimum and maximum values ​​of both groups, calculate the marking of the left group, assuming that the values ​​are on the strait line. Do the same for the right group.
• Go to step 2 with the group that got the widest range, you know that min and max of this group. Do this until the selected group receives no more than 4 values.
• Now you have a group with 4 elements, sorting and finding a solution.

Here is an example of how this algorithm works:

• Entrance: 9 5 3 4 12 9 31 17
• Choose a random number: k = 9
• Sort by smaller and larger k values
• 5 3 4 9 9 12 31 17, k is at index 3
• Left group gape = (9 + 3) / (4 - 1) = 4
• Right group gape = (31 + 9) / (5 - 1) = 10
• We choose the right group 9 9 12 31 17
• Choose a random number: k = 12
• Sort by smaller and larger k values
• 9 9 12 31 17, k is at index 2
• Left group gape = (12 + 9) / (3 - 1) = 11.5
• Right group gape = (31 + 12) / (3 - 1) = 21.5
• The maximum size of 12 31 17 is 31 - 17 = 14

My algorithm is very similar to the Selection Algorithm for finding the index value k of a sorted algorithm in linear time.