Shulou(Shulou.com)06/02 Report--

This article mainly introduces Java how to solve the problem of calculating the maximum difference between two adjacent numbers, which is very detailed and has a certain reference value. Interested friends must finish reading it!

Topic: given an array, find the maximum difference between the two adjacent numbers after sorting. Requires time complexity O (N), and requires that non-comparison-based sorting can not be used.

I checked, temporarily did not find a link to the online OJ, can only write a logarithm, manual test.

When I saw this topic, I said, how is it possible? In an unordered array, find the maximum difference between two adjacent data. But as we all know, the sorting algorithm based on comparison can only reach the level of O (N*logN) as soon as possible, and the topic clearly limits the time complexity to O (N), so if we want to sort based on comparison, and then traverse it after sorting, the time complexity will definitely not meet the requirements.

Some people may also want to say, isn't there a sorting algorithm based on non-comparison? Such as counting sort, cardinality sort, bucket sort. However, the title clearly stipulates that the sorting algorithm based on non-comparison can not be used.

In this case, if you want to use the sorting algorithm to sort, this road is certainly not feasible. We can only think of other ways.

-I'm the dividing line -

Here comes the big show! The flow of the entire code is as follows:

1. First iterate through the array to save the maximum and minimum values of the entire array.

two。 Assuming that there are a total of N elements in the array, then we need to prepare 1 bucket.

In each barrel, a certain range of values can be stored, and the specific range of values that can be stored needs to be calculated with a formula. For example: the first bucket stores 0. The number between 9, the second bucket stores 10. The number of 19.

3. Let's go through the array again and put each number in the corresponding bucket.

Explanation: why do you need to take these three steps? This is a question worth thinking about!

As can be seen from the question, there are a total of N, but we have prepared 1 barrel. In other words, we put each number into the corresponding bucket, even if the N number is in its own bucket, no matter how it is put in, there will always be one more empty bucket.

And we will put each number into the corresponding bucket according to this formula: (ARR [I]-min) * N / (max-min).

In the above formula, we can calculate which bucket the number of I position should be put in. According to the formula, the minimum value must be put in the first bucket, and the maximum value must be put in the last bucket. Well, since the first and last buckets must have data, it means that the empty bucket must be a bucket in the middle.

It is precisely because of the existence of this empty bucket that many kinds of calculation possibilities will be wiped out directly. To be more specific, suppose the storage range of a bucket is 0-9, that is, the bucket can store 10 numbers, and since there is an empty bucket, then the final answer must be greater than 10.

So since it's greater than 10, the two numbers will definitely not be in the same bucket. In this case, we rule out the two data in the bucket, only need to consider the number between the two adjacent buckets, may be the final answer.

In the form of the picture above, put all the data into the corresponding bucket. Because there are empty buckets, our answer must be to subtract the data between two different buckets. When we subtract, we only need to record the maximum and minimum values of each barrel. That is, use the minimum value of the latter barrel to subtract the maximum value of the previous barrel. In this form, loop N times, calculate every two adjacent buckets, and you can get the final answer.

Since we only need the maximum and minimum values in each bucket, we can prepare two arrays, maxs and mins, and store them respectively. The code is as follows:

The above is all the code of this problem, there is not much code, but I think the algorithm idea is really powerful, it is difficult to imagine who thought of this method.

The core lies in the existence of that empty bucket, which obliterates many possibilities. So that the final answer can only exist in the number between two adjacent buckets.

Question: suppose a given array, after calculating the data of the bucket, only one is an empty bucket. So the final answer must be the data of the empty bucket on the right minus the data on the left?

Finally, I put the entire code below, including a logarithm to test the correctness of the above code.

Import java.util.Arrays;public class Code01_CalcTwoNumDiv {public static void main (String [] args) {int testTime = 5000; / / number of tests int N = 50; / / Array length int range = 1000; / / data range boolean flag = true; for (int I = 0; I < testTime; iTunes +) {int [] arr = generateArr (N, range) Int p1 = calcTwoNumDiv (arr); int p2 = sortAfter (arr); if (p1! = p2) {flag = false; break;}} System.out.println (flag? "correct": "error");} public static int calcTwoNumDiv (int [] array) {if (array = = null | | array.length < 2) {return 0;} int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE For (int I: array) {/ / iterate through the array first to find the maximum and minimum values max = Math.max (max, I); min = Math.min (min, I);} if (max = = min) {return 0 / / if the maximum and minimum values are equal, there is only one data in this array} int len = array.length; boolean [] hasNum = new boolean [len + 1]; int [] maxs = new int [len + 1]; int [] mins = new int [len + 1]; / / traversal data for (int I = 0; I < array.length) Int bit +) {int bit = getBit (array [I], len, max, min); / / position of the bucket maxs [bit] = hasNum [bit]? Math.max (maxs [bit], array [I]): array [I]; / / Update maximum mins [bit] = hasNum [bit]? Math.min (mins [bit], array [I]): array [I]; / Update the minimum value hasNum [bit] = true; / / always update to true} / / the first bucket and the last bucket, there must be data. Int preMax = maxs [0]; int res = Integer.MIN_VALUE; / / final result for (int I = 1; I

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.