目录
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^50 <= 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))
}
输出：
3
0
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
基数排序和桶排序都是非比较排序算法，它们的主要区别在于排序的基础方式和结果的处理方式。
基数排序
基数排序是一种按照数字的位数进行排序的算法。它将整数按照位数切割成不同的数字，然后按照每个数字的大小进行排序。基数排序的主要思想是将整数按照位数切割成不同的数字，然后按照每个数字的大小进行排序。基数排序的主要思想是将整数按照位数切割成不同的数字，然后按照每个数字的大小进行排序。
桶排序
桶排序是一种排序算法，它的基本思想是将整数按照某个固定的顺序或者范围进行分配，然后按照分配的结果进行排序。桶排序的主要思想是将整数按照某个固定的顺序或者范围进行分配，然后按照分配的结果进行排序。
基数排序和桶排序的共同点是它们都是非比较排序算法，都是将整数按照某种规则进行排序。它们的不同点在于排序的基础方式和结果的处理方式。基数排序是按照数字的位数进行排序，桶排序是按照固定的顺序或者范围进行排序。基数排序的结果是按照数字的位数进行排序，桶排序的结果是按照固定的顺序或者范围进行排序。
基数排序和桶排序的实现方式也存在差异。基数排序是通过遍历数字来寻找位置，每一次排序都需要进行一次比较。桶排序是通过将数字放入桶中来寻找位置，每一次排序都需要进行一次比较。基数排序的时间复杂度较高，通常需要O(n^2)的时间复杂度，而桶排序的时间复杂度较低，通常只需要O(n)的时间复杂度。