Maximum contiguous difference after sorting an unordered array

Method 1:

Sort the array by O(nlogn) algorithm, and then traverse the sorted array to find the two adjacent elements with the largest travel value

Method 2:

1. Use counting sorting idea to find the interval length of the difference between the maximum value and minimum value, and the offset (minimum value)

2. Create a + 1 array with each element starting at 0

3. Iterate through the array and subtract the offset from each element to obtain the value of the array’s corresponding subscript + 1

4. Iterate through the statistics array and obtain the maximum number of consecutive occurrences of 0 + 1, which is the maximum difference

The code is as follows:

function getMaxSortedDistanceV1(arr:Array<number>):number { let max = arr[0]; let min = arr[0]; for (let index = 1; index < arr.length; index++) { if(arr[index] > max) max = arr[index]; if(arr[index] < min) min = arr[index] } let d = max - min; let countArray = new Array(d + 1).fill(0); for (let index = 0; index < arr.length; index++) { const element = arr[index]; countArray[element - min]++ } let maxDistance = 0; let zeroLength = 0 for (let index = 1; index < countArray.length-1; index++) { if(countArray[index] === 0){ zeroLength++ }else { zeroLength = 0 } if(zeroLength > maxDistance) maxDistance =  zeroLength } return maxDistance + 1 }Copy the code

Counting sort details

Method 3:

Bucket sort is used to solve the limitation of counting sort

1. Create n buckets based on the length n of the array. The interval span of each bucket is (max-min)/(n-1).

2. Traverse the original array, place each element in the corresponding channel, and record the maximum and minimum values of each bucket

3. Iterate over all buckets and calculate the difference between the maximum value of each bucket and the minimum value of non-empty buckets on the right. The maximum value is the largest element xianglin query after sorting the original array

The code is as follows:

function getMaxSortedDistanceV2(arr:Array<number>):number { // 1. Find the maximum and minimum values and calculate the travel values let Max = arr[0]; let min = arr[0]; for (let index = 1; index < arr.length; index++) { if(arr[index] > max) max = arr[index]; if(arr[index] < min) min = arr[index] } let d = max - min; // set bucketNum = arr.length; let bucketArray = new Array(bucketNum); for (let index = 0; index < bucketArray.length; index++) { bucketArray[index] = [] } // 3. Let area = d/(bucketNum - 1) for (let index = 0; index < arr.length; index++) { let num = Math.floor((arr[index] - min)/area) if(bucketArray[num].min === undefined || bucketArray[num].min >  arr[index]) { bucketArray[num].min = arr[index] } if(bucketArray[num].max === undefined || bucketArray[num].max < arr[index]) { bucketArray[num].max = arr[index] } } // 4. Find the biggest difference let leftMax = bucketArray [0]. Max | | 0; let maxDistance = 0; for (let index = 1; index < bucketArray.length; index++) { let rightMin = bucketArray[index].min if(rightMin === undefined) { continue } if((rightMin - leftMax) > maxDistance) { maxDistance = rightMin - leftMax } leftMax = bucketArray[index].min } return maxDistance }Copy the code

Bucket sorting in detail

Summary from: the journey of cartoon algorithm xiao Grey algorithm