給定一個數組，求如果排序之后，相鄰兩數的最大差值，要求時間復雜度O(N)，且要求不能用非基于比較的排序。

import java.util.Arrays;public class MaximumDifferenceBetweenAdjacentNumbers{public static int maxGap(int[] nums){if (nums == null || nums.length < 2) {return 0;}int len = nums.length;int min = Integer.MAX_VALUE;int max = Integer.MIN_VALUE;for (int i = 0; i < len; i++){min = Math.min(min, nums[i]);max = Math.max(max, nums[i]);}if (min == max){return 0;}int bid = 0;int[] maxs = new int[len + 1];int[] mins = new int[len + 1];boolean[] hasNum = new boolean[len + 1];for (int i = 0; i < len; i++) {bid = bucket(nums[i], len, min, max);mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];hasNum[bid] = true;}int res = 0;int lastMax = maxs[0];for (int i = 1; i < len + 1; i++) {if (hasNum[i]){res = Math.max(res, mins[i] - lastMax);lastMax = maxs[i];}}return res;}public static int bucket(long num, long len, long min, long max) {return (int)((num - min) * len / (max - min));}public static int comparator(int[] nums) {if(nums == null || nums.length < 2) {return 0;}Arrays.sort(nums);int res = Integer.MIN_VALUE;for (int i = 1; i < nums.length; i++) {res = Math.max(res, nums[i] - nums[i - 1]);}return res;}public static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize+1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int)((maxValue+1) * Math.random()) - (int) (maxValue) * Math.random();}return arr;}public static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}public static void main(String[] args) {boolean succeed = true;int testTime = 700000, maxSize = 100, maxValue = 100;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);if (maxGap(arr1) != comparator(arr2)) {succeed = false;break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");} }

總結

以上是生活随笔為你收集整理的给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N)，且要求不能用非基于比较的排序。的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。