然而很可惜,Go的Map没有排序功能,不像Java可以直接用TreeMap来解决问题。因此上面的方法是错的。后来我想了想,其实可以利用数组,令下标为key,那么就能实现有序了。因此,我写出了第二版程序:
package main
import "fmt"
func main() {
num := 0
fmt.Scan(&num)
a := 0
b := 0
arr := make([]int, 11111112)
for i := 0; i < num; i++ {
fmt.Scan(&a)
fmt.Scan(&b)
arr[a] += b
for i, v := range arr {
if v != 0 {
fmt.Printf("%d %d\n", i, v)
这样的判定就正确了,但是问题又来了,时间上太久了:
Java版本的才100ms,Go竟然要60ms,这实际上是因为数组太大了导致的。为了解决这个问题,还需要引入一个Map:
将所有的输入保存到Map中
将key保存到一个数组中
遍历数组,用数组中的元素访问之前的Map
新的代码是这样的:
package main
import (
"fmt"
"sort"
func main() {
num := 0
fmt.Scan(&num)
a := 0
b := 0
m := make(map[int]int)
for i := 0; i < num; i++ {
fmt.Scan(&a)
fmt.Scan(&b)
m[a] += b
var arr []int
for k := range m {
arr = append(arr, k)
sort.Ints(arr)
for _, v := range arr {
fmt.Printf("%d %d\n", v, m[v])