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 上提交的结果却是第一种消耗的内存更低些, 这是为什么呢?
这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。
V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.