请教一个 leetcode 上 Go 的内存消耗的问题

2022-06-25 14:16:56 +08:00
 moonheart

https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array

给你一个含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字,并以数组的形式返回结果。

这道题两种解法, 第一种使用额外的数组来保存, 第二种直接在原始数组上存储:

func findDisappearedNumbers1(nums []int) (res []int) {
	x := make([]int, len(nums))
	for _, num := range nums {
		x[num-1] = num
	}
	for i, n := range x {
		if n == 0 {
			res = append(res, i+1)
		}
	}
	return
}


func findDisappearedNumbers2(nums []int) (res []int) {
	l := len(nums)
	for _, num := range nums {
		nums[(num-1)%l] += l
	}
	for i, n := range nums {
		if n <= l {
			res = append(res, i+1)
		}
	}
	return
}

按理说, 第二种使用的内存会低一些, 使用 go benchmem 也可以看到 第一种 3 allocs/op, 第二种 2 allocs/op:

goos: windows
goarch: amd64
cpu: AMD Ryzen 5 5600X 6-Core Processor
Benchmark1-12           20885110                57.44 ns/op           88 B/op          3 allocs/op
Benchmark2-12           21033442                58.17 ns/op           24 B/op          2 allocs/op

但是在 leetcode 上提交的结果却是第一种消耗的内存更低些, 这是为什么呢?

1820 次点击
所在节点    Go 编程语言
3 条回复
111qqz
2022-06-25 14:19:34 +08:00
看 leetcode 的耗时和内存没意义,时间空间复杂度是对的就行吧
moonheart
2022-06-25 14:30:03 +08:00
@111qqz #1 懂了,谢谢大佬
Itoktsnhc
2022-06-25 15:30:47 +08:00
leetcode 的耗时和内存仅在对比的时候有点用,有些时候题目还会加强数据集或者升级版本,都会导致性能有差距

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/862115

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX