无序数组排序后的最大相邻值

题目：无序数组排序后的最大相邻差值

解法1：

对数组进行 O(nlogn) 的算法排序，再对排序后的数组遍历，找出差值最大的两个相邻元素

解法2：

1. 利用计数排序思想，找到最大值和最小值的差值为区间长度，以及偏移量(最小值)

2. 创建区间长度 + 1 的统计数组，每个元素初始值为 0

3. 遍历原数组，每个元素 减去偏移量 得出的值 则 统计数组相应下标的值 + 1

4. 遍历统计数组，得出最大连续出现 0 的次数 + 1，即为最大差值

代码如下：

  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
  }
复制代码

计数排序详解

解法3：

利用桶排序，解决计数排序的局限性

1. 根据数组的长度 n，创建出 n 个桶，则每个桶的区间的区间跨度 为 (max – min)/(n – 1)

2. 遍历原数组，把每个元素放到对应的通内，记录每个桶的最大值和最小值

3. 遍历所有桶，统计每个桶的最大值和右侧非空桶的最小值的差，最大的即为原数组排序后的最大元素祥林查

代码如下：

function getMaxSortedDistanceV2(arr:Array<number>):number {
    // 1. 找出最大和最小值 并计算出差值
    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;


    // 2. 初始化桶
    let 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. 找到最大差值
    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
}
复制代码

桶排序详解

摘要总结自: 漫画算法 小灰的算法之旅