HJ3 明明的随机数

牛客网：HJ3 明明的随机数
https://www.nowcoder.com/practice/3245215fffb84b7b81285493eae92ff0?tpId=37&tqId=21226&ru=/exam/oj

使用Go语言解题，最简单的方式：
解题一：

// 运行时间：5ms 占用内存：1180KB
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	num := make([]int, 0, n)
	_, _ = fmt.Scan(&n)
	set := make(map[int]struct{}, n)
	for i := 0; i < n; i++ {
		var tmp int
		_, _ = fmt.Scan(&tmp)
		if _, ok := set[tmp]; ok {
			continue // 重复值跳过
		}
		set[tmp] = struct{}{}
		num = append(num, tmp)
	}
	sort.Ints(num)
	for _, number := range num {
		fmt.Println(number)
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

解题比较暴力，直接去重后再排序，思索后，觉得应该有所优化，从样例数据来看，数据量并不大，似乎可以用哈希表解题；
解题二：

// 运行时间：5ms 占用内存：1052KB
package main

import (
	"fmt"
)

func main() {
	var n int
	_, _ = fmt.Scan(&n)
	set := make([]int, 500, 500)
	for i := 0; i < n; i++ {
		var tmp int
		_, _ = fmt.Scan(&tmp)
		set[tmp] = tmp
	}
	for _, number := range set {
		if number != 0 {
			fmt.Println(number)
		}

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

提交后，发现与第一种代码的运行时间和内存占比相差不大，开始查阅排行榜大哥代码，发现耗时原因出现在数据的录入上，修改代码重新提交
解题三：

//运行时间：4ms 占用内存：1308KB
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	scan := bufio.NewScanner(os.Stdin)
	scan.Scan()
	if len(scan.Text())==0{
		return
	}
	n,_:=strconv.Atoi(scan.Text())
	set := make([]int, 500, 500)
	for i := 0; i < n; i++ {
		scan.Scan()
		tmpStr := scan.Text()
		tmp,_:=strconv.Atoi(tmpStr)
		set[tmp] = tmp
	}
	for _, number := range set {
		if number != 0 {
			fmt.Println(number)
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

运行时间缩短了1ms，内存涨了250kb,再次修改代码
解题四：

// 运行时间：4ms 占用内存：1096KB
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	scan := bufio.NewScanner(os.Stdin)
	scan.Scan()
	if len(scan.Text())==0{
		return
	}
	n,_:=strconv.Atoi(scan.Text())
	set := make([]bool, 500, 500)
	for i := 0; i < n; i++ {
		scan.Scan()
		tmpStr := scan.Text()
		tmp,_:=strconv.Atoi(tmpStr)
		set[tmp] = true
	}
	for number, v := range set {
		if v == true {
			fmt.Println(number)
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

内存缩小，时间未变，不太理解，找到排行榜第一的代码进行提交，终于找到原因：

相同的代码，运行时间差距和内存差距，存在于牛客网的测评机，与代码无关，放弃挣扎；使用哈希表和sort在数据量不大的情况下，解决这道题，没有过多优化。