这是一个创建于 1206 天前的主题，其中的信息可能已经有所发展或是发生改变。
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 上提交的结果却是第一种消耗的内存更低些, 这是为什么呢?
 | 1 midasplus 2022-06-25 14:19:34 +08:00 via Android 看 leetcode 的耗时和内存没意义，时间空间复杂度是对的就行吧 |
 | 3 Itoktsnhc 2022-06-25 15:30:47 +08:00 leetcode 的耗时和内存仅在对比的时候有点用，有些时候题目还会加强数据集或者升级版本，都会导致性能有差距 |
Select Language