LeetCode中级算法-排序和搜索（2）
合并区间
[题目]
给出一个区间的集合，请合并所有重叠的区间。
[输入1]
intervals = [[1,3],[2,6],[8,10],[15,18]] [返回1]
[[1,6],[8,10],[15,18]][输入2]
intervals = [[1,4],[4,5]][返回2]
[[1,5]][解法]
首先按照小范围的左边界进行升序排序，排序完成以后，遍历新的范围，可以放入合并队列的条件：
1. 合并队列中尚无元素
2. 当前遍历到的小范围的左边界要比合并队列中最后一个范围的左边界还要大
不满足上面的条件的，说明是和合并队列中最后一个范围有重合，只需要更新合并队列中最后一个范围的右边界为最大值
[代码实现]
package main
import (
"fmt"
"sort"
)
func main() {
input := [][]int {{1,3},{2,6},{8,10},{15,18}}
result := computeResult(input)
fmt.Println("result:", result)
}
type ISort [][]int
func (sort ISort) Len() int {
return len(sort)
}
func (sort ISort) Less(i, j int) bool {
return sort[i][0] < sort[j][0]
}
func (sort ISort) Swap(i, j int) {
sort[i], sort[j] = sort[j], sort[i]
}
func computeResult(input [][]int) [][]int {
// 首先对原集合的左边界进行升序排列
aInput := ISort{}
for _, item := range input {
aInput = append(aInput, item)
}
sort.Sort(aInput)
result := [][]int {}
for i := 0; i < len(aInput); i++ {
// 当前小范围的左右边界
left, right := aInput[i][0], aInput[i][1]
// 当前合并队列的长度
resLen := len(result)
// 直接可以放入合并队列的条件：
// 1. 合并队列中第一个范围
// 2. 当前小范围的左边界，要比合并队列中最后一个范围的右边界要大
if resLen == 0 || result[resLen - 1][1] < left {
result = append(result, []int {left, right})
} else {
// 选取右边界中比较大的那个更新上来
result[resLen - 1][1] = max(result[resLen - 1][1], aInput[i][1])
}
}
return resul
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}搜索旋转排序数组
[题目]
升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。
请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
[输入1]
nums = [4,5,6,7,0,1,2], target = 0[返回1]
4[输入2]
nums = [4,5,6,7,0,1,2], target = 3[返回2]
-1[解法]
设置一个mid指针，通过判断数组中下标为mid的元素和左右边界以及target之间的关系，确定mid向左定界，还是想有定界，直到mid指向的元素等于target，则找到了target的下标，否则没有该元素。
此题目要求在O(logn)时间内完成搜索，所以要是用二分查找，二分查找就需要引入mid = (left + right) / 2，在这个基础上，通过判断target和左右边界的位置，确定下一轮left和right的边界位置
[代码实现]
package main
import "fmt"
func main() {
input := []int {4,5,6,7,0,1,2}
target := 0
result := computeResult(target, input)
fmt.Println("result:", result)
}
func computeResult(target int, input []int) int {
left, right := 0, len(input) - 1
count := len(input)
for left <= right {
mid := (left + right) / 2
if input[mid] == target {
return mid
}
if input[0] < input[mid] {
// 这种情况target肯定在left和mid之间
if input[0] <= target && target < input[mid] {
right = mid - 1
} else {
left = mid + 1
}
} else {
if input[mid] < target && target <= input[count - 1] {
// 这种情况下target肯定在mid到right之间
left = mid + 1
} else {
right = mid - 1
}
}
}
return -1
}搜索二维矩阵
[题目]
升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。
请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
[输入1]
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5[返回1]
true[输入2]
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20[返回2]
false
[解法1]
每行进行二分查找, 遍历整个二维矩阵，这样时间复杂度O(nlogn)
[代码实现1]
func computeResult(target int, input [][]int) bool {
count := len(input)
for i := 0; i < count; i++ {
if _compute(target, input[i]) {
return true
}
}
return false
}
func _compute(target int, input []int) bool {
left := 0
right := len(input) - 1
for left <= right {
mid := (left + right) / 2
if input[mid] == target {
return true
}
if input[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return false
}[解法2]
从右上角开始同时移动横向和纵向的两个指针，直到找到和target相同的元素，这种算法的时间复杂度是O(m + n),但是需要注意的是，需要保证在遍历的时候两个方向的升序、降序方式是相反的，这样可以不考虑回退，即从左下角或者右上角开始向对向方向遍历，若横纵向遍历的顺序一致，那么坐标的移动将变得困难重重
[代码实现2]
func computeResult2(target int,input [][]int) bool {
rowCount := len(input)
colCount := len(input[0])
rowIndex := 0
colIndex := colCount - 1
for rowIndex < rowCount && colIndex >= 0 {
if target < input[rowIndex][colIndex] {
colIndex--
} else if target > input[rowIndex][colIndex] {
rowIndex++
} else {
return true
}
}
return false
}[代码测试]
package main
import "fmt"
func main() {
input := [][]int {
{1,4,7,11,15},
{2,5,8,12,19},
{3,6,9,16,22},
{10,13,14,17,24},
{18,21,23,26,30},
}
target := 5
result := computeResult(target, input)
fmt.Println("result:", result)
result2 := computeResult2(target, input)
fmt.Println("result:", result2)
}