Golang Go语言中请教一个 leetcode 上的内存消耗问题

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 上提交的结果却是第一种消耗的内存更低些, 这是为什么呢?

image image


Golang Go语言中请教一个 leetcode 上的内存消耗问题

更多关于Golang Go语言中请教一个 leetcode 上的内存消耗问题的实战教程也可以访问 https://www.itying.com/category-94-b0.html

4 回复

看 leetcode 的耗时和内存没意义，时间空间复杂度是对的就行吧

更多关于Golang Go语言中请教一个 leetcode 上的内存消耗问题的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


#1 懂了，谢谢大佬

leetcode 的耗时和内存仅在对比的时候有点用，有些时候题目还会加强数据集或者升级版本，都会导致性能有差距

在LeetCode上使用Go语言解决算法问题时，内存消耗的优化通常涉及多个方面，包括但不限于数据结构的选择、算法逻辑的改进以及内存管理的精细控制。以下是一些建议，帮助你减少内存消耗：

  1. 选择合适的数据结构：

    • 优先使用内存占用较小的数据结构，例如使用切片（slice）而不是数组（array），因为切片在动态扩展时更加高效。
    • 对于需要频繁查找的场景，考虑使用哈希表（map）来替代链表或数组，以降低时间复杂度并间接减少内存使用（因为减少了不必要的遍历）。

  2. 优化算法逻辑：

    • 尝试减少不必要的变量和中间结果的存储。
    • 利用原地算法（in-place algorithm）来减少额外的空间开销。
    • 分析算法的时间复杂度和空间复杂度，寻找更优的解法。

  3. 精细控制内存管理：

    • 避免内存泄漏，及时释放不再使用的资源。
    • 在处理大数据集时，考虑使用流式处理或分批处理来减少内存占用。
    • 使用Go的内置函数（如copy）来高效地复制切片，避免不必要的内存分配。

  4. 利用Go的特性：

    • Go的编译器和运行时已经做了很多内存管理的优化，但你可以通过了解Go的内存模型来更好地编写高效的代码。
    • 使用Go的sync包中的数据结构（如sync.Map）来在多线程环境中安全地共享数据，同时减少内存开销。

总之，优化内存消耗需要综合考虑数据结构、算法逻辑和内存管理等多个方面。希望这些建议能对你有所帮助！

回到顶部