Golang每日一练(leetDay0057) 缺失区间、最大间距

2023-05-29 179

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Golang每日一练(leetDay0057) 缺失区间、最大间距

163. 缺失的区间 Missing Ranges

给定一个排序的整数数组 nums ，其中元素的范围在闭区间 [lower, upper] 当中，返回不包含在数组中的缺失区间。

示例：

输入: nums = [0, 1, 3, 50, 75], lower = 0, upper = 99

输出: [“2”, “4->49”, “51->74”, “76->99”]

代码1：

package main
import (
  "fmt"
  "strconv"
)
func findMissingRanges(nums []int, lower int, upper int) []string {
  res := make([]string, 0)
  start := lower - 1
  for i := 0; i <= len(nums); i++ {
    end := upper + 1
    if i < len(nums) {
      end = nums[i]
    }
    if end-start == 2 {
      res = append(res, strconv.Itoa(start+1))
    } else if end-start > 2 {
      res = append(res, strconv.Itoa(start+1)+"->"+strconv.Itoa(end-1))
    }
    start = end
  }
  return res
}
func main() {
  nums := []int{0, 1, 3, 50, 75}
  lower := 0
  upper := 99
  fmt.Println(findMissingRanges(nums, lower, upper))
}

代码2：

package main
import (
  "fmt"
  "strconv"
)
func findMissingRanges(nums []int, lower int, upper int) []string {
  res := make([]string, 0)
  start := lower
  for i := 0; i < len(nums); i++ {
    if nums[i] < start {
      continue
    }
    if nums[i] == start {
      start++
      continue
    }
    end := nums[i] - 1
    if start == end {
      res = append(res, strconv.Itoa(start))
    } else {
      res = append(res, strconv.Itoa(start)+"->"+strconv.Itoa(end))
    }
    start = nums[i] + 1
  }
  if start <= upper {
    if start == upper {
      res = append(res, strconv.Itoa(start))
    } else {
      res = append(res, strconv.Itoa(start)+"->"+strconv.Itoa(upper))
    }
  }
  return res
}
func main() {
  nums := []int{0, 1, 3, 50, 75}
  lower := 0
  upper := 99
  fmt.Println(findMissingRanges(nums, lower, upper))
}

输出：

[2 4->49 51->74 76->99]

164. 最大间距 Maximum Gap

给定一个无序的数组 nums，返回数组在排序之后，相邻元素之间最大的差值。如果数组元素个数小于 2，则返回 0 。

您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

示例 1:

输入: nums = [3,6,9,1]

输出: 3

解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

示例 2:

输入: nums = [10]

输出: 0

解释: 数组元素个数小于 2，因此返回 0。

提示:

1 <= nums.length <= 10^5

0 <= nums[i] <= 10^9

代码1：基数排序

package main
import "fmt"
func maximumGap(nums []int) int {
  n := len(nums)
  if n < 2 {
    return 0
  }
  maxNum := nums[0]
  for _, num := range nums {
    if num > maxNum {
      maxNum = num
    }
  }
  exp := 1
  buf := make([]int, n)
  for maxNum/exp > 0 {
    count := make([]int, 10)
    for _, num := range nums {
      digit := (num / exp) % 10
      count[digit]++
    }
    for i := 1; i < 10; i++ {
      count[i] += count[i-1]
    }
    for i := n - 1; i >= 0; i-- {
      digit := (nums[i] / exp) % 10
      count[digit]--
      buf[count[digit]] = nums[i]
    }
    copy(nums, buf)
    exp *= 10
  }
  maxGap := 0
  for i := 1; i < n; i++ {
    gap := nums[i] - nums[i-1]
    if gap > maxGap {
      maxGap = gap
    }
  }
  return maxGap
}
func main() {
  nums := []int{3, 6, 9, 1}
  fmt.Println(maximumGap(nums))
  nums = []int{10}
  fmt.Println(maximumGap(nums))
}

代码2：桶排序

package main
import "fmt"
func maximumGap(nums []int) int {
  n := len(nums)
  if n < 2 {
    return 0
  }
  minNum, maxNum := nums[0], nums[0]
  for _, num := range nums {
    if num < minNum {
      minNum = num
    } else if num > maxNum {
      maxNum = num
    }
  }
  if minNum == maxNum {
    return 0
  }
  bucketSize := max(1, (maxNum-minNum)/(n-1))
  bucketNum := (maxNum-minNum)/bucketSize + 1
  buckets := make([][]int, bucketNum)
  for _, num := range nums {
    bucketIndex := (num - minNum) / bucketSize
    if buckets[bucketIndex] == nil {
      buckets[bucketIndex] = []int{num, num}
    } else {
      if num < buckets[bucketIndex][0] {
        buckets[bucketIndex][0] = num
      } else if num > buckets[bucketIndex][1] {
        buckets[bucketIndex][1] = num
      }
    }
  }
  maxGap := 0
  prevMax := minNum
  for _, bucket := range buckets {
    if bucket != nil {
      maxGap = max(maxGap, bucket[0]-prevMax)
      prevMax = bucket[1]
    }
  }
  return maxGap
}
func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}
func main() {
  nums := []int{3, 6, 9, 1}
  fmt.Println(maximumGap(nums))
  nums = []int{10}
  fmt.Println(maximumGap(nums))
}