“This is the 14th day of my participation in the First Challenge 2022.

[B] [C] [D]

Given an unordered array, find the largest difference between adjacent elements of the array after sorting.

If the number of elements is less than 2, 0 is returned.

Example 1:

Input: [3,6,9,1] output: 3 explanation: the sorted array is [1,3,6,9], where there is a maximum difference of 3 between adjacent elements (3,6) and (6,9).Copy the code

Example 2:

Input: [10] Output: 0 Explanation: The number of elements in the array is less than 2, so return 0.Copy the code

Description:

  • You can assume that all elements in the array are non-negative integers and that the values are in the range of 32-bit signed integers.
  • Try to solve this problem with linear time and space complexity.

Their thinking

The question gives the following information:

  • All elements of an array are non-negative integers
  • The value is in the range of 32 – bit signed integers

Requirements are given:

  • This problem is solved in linear time complexity and space complexity

Since we’re looking for the maximum difference between the elements of the sorted array, we’re going to sort the input array. The time complexity and space complexity of our algorithm should be O(n), while the time complexity of sorting algorithm is O(n), we can think of counting sort and radix sort. So if we use count sort, the open count array will be very large. So we can sort the input array using radix sort, and then iterate over the sorted result to get the maximum difference.

Code implementation

Function low16(num){return num & 0xFFFF} function high16(num){return (num & 0xFFff0000) >> 16 } var maximumGap = function (nums) {const len = nums.length; If (len<2) return 0; // Create count Array const count = Array(65536).fill(0), Temp = Array(len) temp = Array(len) temp = Array(len) temp = Array(len) i<len; I++) count [low16 (nums [I]]] + + / / prefix and the for (let I = 1; i<65536; I++) count [I] + = count [I - 1) / / place for (let I = len - 1; i>=0; Temp [--count[low16(nums[I])]] = nums[I] i < 65536; I ++) count[I] = 0 for(let I = 0; i<len; I++) count [high16 (temp) [I]] + + / / prefix and the for (let I = 1; i<65536; I++) count [I] + = count [I - 1) / / place for (let I = len - 1; i>=0; I --) nums[--count[high16(temp[I])]] = temp[I] i < len; I ++) res = math.max (res, nums[I] -nums [I - 1])Copy the code

At this point we have leetcode-164- maximum spacing

If you have any questions or suggestions, please leave a comment! 👏 🏻 👏 🏻 👏 🏻