0%

桶

发表于 更新于 分类于

桶问题

基于非比较的排序

  1. 计数排序
    • 思想:
      1. 找到数组的最大值
      2. 创建一个最大值+1的辅助数组, 并初始化为1
      3. 遍历数组, 每得到一个数,就在这个数的辅助数组位置的值加1
      4. 根据辅助数组的数量写回原数组
    • 代码: (本来太简单不想写来, 但是因为太简单, 还是写一下吧)
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      func countSort(arr []int) {
          if arr == nil || len(arr) < 2 {
              return
          }
          help := make([]int, len(arr) + 1)
          for i := 0; i < len(arr); i++ {
              help[arr[i]]++
          }
          index := 0
          for i := 0; i <len(help); i++ {
              for help[i] > 0 {
                  arr[index] = i
                  help[i]--
                  index++
              }
          }
      }
    • 复杂度
      1. 时间复杂度: O(N), 需要对数组遍历两次
      2. 空间复杂度: O(N), 需要创建一个辅助数组

求一个无序数组排序后相邻两个数的差的最大值

  • 问题描述:
    给定一个无序的数组, 请返回排序后相邻两个数的差的最大值
  • 思路:
    1. 创建桶, 桶的个数为数组长度加1
    2. 找到最大值和最小值
    3. 最小值放第一个桶, 最大值放最后一个桶, 然后根据最小值和最大值划分桶的范围
    4. 遍历所有的桶, 每次都找下一个不空的桶, 计算本桶最大值和下一个桶最小值的差, 记录最大的差
  • 解释:
    1. 桶的个数为数组长度加1可以保证一定会有一个桶是空的(有可能不止一个)
    2. 因为会有桶是空的, 所以这个最大的差值一定不在同一个桶里
    3. 最大最小值放两边的桶里, 可以保证空的桶一定不在两边
  • 代码:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    func getSortMinSub(arr []int) int {
    	if arr == nil || len(arr) < 2 {
    		return 0
    	}
    	const (
    		INT_MAX = int(^uint32(0) >> 1)
    		INT_MIN = ^INT_MAX
    	)
    	max, min := INT_MIN, INT_MAX
    	for i := 0; i < len(arr); i++ {
    		if arr[i] > max {
    			max = arr[i]
    		}
    		if arr[i] < min {
    			min = arr[i]
    		}
    	}
    	maxBarrel, minBarrel := make([]int, len(arr) + 1), make([]int, len(arr) + 1)
    	isHaveNum := make([]bool, len(arr) + 1)
    	for i := 0; i < len(arr); i++ {
    		index := getBarrelNum(arr[i], max, min, len(arr))
    		if !isHaveNum[index] {
    			isHaveNum[index] = true
    			maxBarrel[index] = arr[i]
    			minBarrel[index] = arr[i]
    		} else {
    			if maxBarrel[index] < arr[i] {
    				maxBarrel[index] = arr[i]
    			}
    			if minBarrel[index] > arr[i] {
    				minBarrel[index] = arr[i]
    			}
    		}
    	}
    	res := INT_MIN
    	lastMaxValue := maxBarrel[0]
    	for i := 1; i < len(isHaveNum); i++ {
    		if isHaveNum[i] {
    			tmp := minBarrel[i] - lastMaxValue
    			if tmp > res {
    				res = tmp
    			}
    			lastMaxValue = maxBarrel[i]
    		}
    	}
    	return res
    }

    func getBarrelNum(num, max, min, len int) int {
    	return int((num - min) * len / (max - min))
    }
  • 代码解释:
    只解释一下getBarrelNum函数, 笔者在写这段代码的时候并没有完全理解, 只能说个大概, 这句代码的意思就是求目标值在最小值和最大值的比例是哪, 然后这个比例乘上桶的最大索引就是该值的桶的目标索引