主体思路
用二分查找
注意细节
注意题目要求的答案输出格式
基本代码
package main
import (
"bufio"
"os"
"fmt"
)
var (
n, q, tmp int
nums []int
in = bufio.NewReader(os.Stdin)
out = bufio.NewWriter(os.Stdout)
)
func mySearch(x int) []int {
ans := []int{}
l, r := 0, n // [0...n - 1] + [n] 找开始
for l < r {
mid := l + (r - l) >> 1
if nums[mid] >= x {
r = mid
} else { l = mid + 1 }
}
ans = append(ans, r)
l, r = -1, n - 1 // [-1] + [0...n - 1] 找结尾
for l < r {
mid := l + (r - l) + 1 >> 1
if nums[mid] <= x {
l = mid
} else { r = mid - 1 }
}
ans = append(ans, r)
if ans[0] > ans[1] { return []int{-1, -1} }
return ans
}
func main() {
fmt.Fscan(in, &n, &q)
nums = make([]int, n)
for i := 0; i < n; i++ { fmt.Fscan(in, &nums[i]) }
for i := 0; i < q; i++ {
fmt.Fscan(in, &tmp)
ans := mySearch(tmp)
fmt.Fprintln(out, ans[0], ans[1])
}
out.Flush()
}
“邪道”做法: 用sort包
还挺快的
package main
import (
"bufio"
"os"
"fmt"
"sort"
)
var (
n, q, tmp int
nums []int
in = bufio.NewReader(os.Stdin)
out = bufio.NewWriter(os.Stdout)
)
func mySearch(x int) []int {
var (
l = sort.SearchInts(nums, x)
r = sort.SearchInts(nums, x + 1) - 1
)
if l == n || nums[l] != x { return []int{-1, -1} }
return []int{l, r}
}
func main() {
fmt.Fscan(in, &n, &q)
nums = make([]int, n)
for i := 0; i < n; i++ { fmt.Fscan(in, &nums[i]) }
for i := 0; i < q; i++ {
fmt.Fscan(in, &tmp)
ans := mySearch(tmp)
fmt.Fprintln(out, ans[0], ans[1])
}
out.Flush()
}