目录
229. 多数元素 II Majority Element ii 🌟🌟
228. 汇总区间 Summary Ranges
给定一个 无重复元素 的 有序 整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出：
"a->b"，如果a != b"a"，如果a == b
示例 1：
输入：nums = [0,1,2,4,5,7] 输出：["0->2","4->5","7"] 解释：区间范围是： [0,2] --> "0->2" [4,5] --> "4->5" [7,7] --> "7"
示例 2：
输入：nums = [0,2,3,4,6,8,9] 输出：["0","2->4","6","8->9"] 解释：区间范围是： [0,0] --> "0" [2,4] --> "2->4" [6,6] --> "6" [8,9] --> "8->9"
提示：
0 <= nums.length <= 20-2^31 <= nums[i] <= 2^31 - 1nums中的所有值都 互不相同nums按升序排列
代码1： 暴力枚举
package main
import (
"fmt"
"strconv"
)
func summaryRanges(nums []int) []string {
res := []string{}
if len(nums) == 0 {
return res
}
i := 0
for i < len(nums) {
j := i
for j < len(nums)-1 && nums[j+1]-nums[j] == 1 {
j++
}
if i == j {
res = append(res, strconv.Itoa(nums[i]))
} else {
res = append(res, strconv.Itoa(nums[i])+"->"+strconv.Itoa(nums[j]))
}
i = j + 1
}
return res
}
func main() {
nums := []int{0, 1, 2, 4, 5, 7}
fmt.Println(summaryRanges(nums))
nums = []int{0, 2, 3, 4, 6, 8, 9}
fmt.Println(summaryRanges(nums))
}
代码2： 双指针
package main
import (
"fmt"
"strconv"
)
func summaryRanges(nums []int) []string {
res := []string{}
if len(nums) == 0 {
return res
}
i, j := 0, 0
for j < len(nums) {
if j < len(nums)-1 && nums[j+1]-nums[j] == 1 {
j++
} else {
if i == j {
res = append(res, strconv.Itoa(nums[i]))
} else {
res = append(res, strconv.Itoa(nums[i])+"->"+strconv.Itoa(nums[j]))
}
j++
i = j
}
}
return res
}
func main() {
nums := []int{0, 1, 2, 4, 5, 7}
fmt.Println(summaryRanges(nums))
nums = []int{0, 2, 3, 4, 6, 8, 9}
fmt.Println(summaryRanges(nums))
}
代码3： 字符串拼接
package main
import (
"fmt"
"strconv"
)
func summaryRanges(nums []int) []string {
res := []string{}
if len(nums) == 0 {
return res
}
i, j := 0, 0
for j < len(nums) {
if j < len(nums)-1 && nums[j+1]-nums[j] == 1 {
j++
} else {
if i == j {
res = append(res, strconv.Itoa(nums[i]))
} else {
res = append(res, fmt.Sprintf("%d->%d", nums[i], nums[j]))
}
j++
i = j
}
}
return res
}
func main() {
nums := []int{0, 1, 2, 4, 5, 7}
fmt.Println(summaryRanges(nums))
nums = []int{0, 2, 3, 4, 6, 8, 9}
fmt.Println(summaryRanges(nums))
}
代码4： 迭代器
package main
import (
"fmt"
"strconv"
)
func summaryRanges(nums []int) []string {
res := []string{}
if len(nums) == 0 {
return res
}
iter, i := nums[1:], nums[0]
for len(iter) > 0 {
if iter[0]-i == 1 {
iter, i = iter[1:], iter[0]
} else {
if i == nums[0] {
res = append(res, strconv.Itoa(i))
} else {
res = append(res, fmt.Sprintf("%d->%d", nums[0], i))
}
nums, iter, i = iter, iter[1:], iter[0]
}
}
if i == nums[0] {
res = append(res, strconv.Itoa(i))
} else {
res = append(res, fmt.Sprintf("%d->%d", nums[0], i))
}
return res
}
func main() {
nums := []int{0, 1, 2, 4, 5, 7}
fmt.Println(summaryRanges(nums))
nums = []int{0, 2, 3, 4, 6, 8, 9}
fmt.Println(summaryRanges(nums))
}
输出：
[0->2 4->5 7]
[0 2->4 6 8->9]
229. 多数元素 II Majority Element ii
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1：
输入：[3,2,3] 输出：[3]
示例 2：
输入：[1] 输出：[1]
示例 3：
输入：[1,2] 输出：[1,2]
提示：
1 <= nums.length <= 5 * 10^4-10^9 <= nums[i] <= 10^9
进阶：
- 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
相关题目：
代码1： 哈希表
package main
import "fmt"
func majorityElement(nums []int) []int {
n := len(nums)
if n == 0 {
return []int{}
}
res := []int{}
count := make(map[int]int)
for _, num := range nums {
count[num]++
}
for key, val := range count {
if val > n/3 {
res = append(res, key)
}
}
return res
}
func main() {
nums := []int{3, 2, 3}
fmt.Println(majorityElement(nums))
nums = []int{1}
fmt.Println(majorityElement(nums))
nums = []int{1, 2}
fmt.Println(majorityElement(nums))
}
代码2： 排序
package main
import (
"fmt"
"sort"
)
func majorityElement(nums []int) []int {
n := len(nums)
if n == 0 {
return []int{}
}
res := []int{}
sort.Ints(nums)
var num, count int
for i := 0; i < n; i++ {
if nums[i] == num {
count++
} else {
if count > n/3 {
res = append(res, num)
}
num, count = nums[i], 1
}
}
if count > n/3 {
res = append(res, num)
}
return res
}
func main() {
nums := []int{3, 2, 3}
fmt.Println(majorityElement(nums))
nums = []int{1}
fmt.Println(majorityElement(nums))
nums = []int{1, 2}
fmt.Println(majorityElement(nums))
}
代码3： 摩尔投票法
package main
import "fmt"
func majorityElement(nums []int) []int {
n := len(nums)
if n == 0 {
return []int{}
}
res := []int{}
var num1, num2, count1, count2 int
for _, num := range nums {
if num == num1 {
count1++
} else if num == num2 {
count2++
} else if count1 == 0 {
num1 = num
count1 = 1
} else if count2 == 0 {
num2 = num
count2 = 1
} else {
count1--
count2--
}
}
count1, count2 = 0, 0
for _, num := range nums {
if num == num1 {
count1++
} else if num == num2 {
count2++
}
}
if count1 > n/3 {
res = append(res, num1)
}
if count2 > n/3 {
res = append(res, num2)
}
return res
}
func main() {
nums := []int{3, 2, 3}
fmt.Println(majorityElement(nums))
nums = []int{1}
fmt.Println(majorityElement(nums))
nums = []int{1, 2}
fmt.Println(majorityElement(nums))
}
输出：
[3]
[1]
[1 2]
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/