Golang中如何避免使用嵌套循环？

Golang中如何避免使用嵌套循环？ 你好，我刚开始学习Go语言，想在这里请教一个问题。我在解决CodeFights上的一个问题时，虽然得到了正确答案，但无法让代码在4秒内执行完成。我猜想可能有比嵌套循环更好的方法？

以下是Go Playground的链接和代码展示。如果有什么明显需要改进的地方，我也很乐意听取建议。

Go Playground: https://play.golang.org/p/AT1EllmUhMI

package main

import (
	"fmt"
)

//find the number that is duplicated first in the array

func firstDuplicate(a []int) int {
    s := []int{}
	for _, fVal := range a {
		for _, val := range s {
			if val == fVal {
				return val
			}
		}
		s = append(s, fVal)
	}
	return -1
}

func main() {
c := []int{2, 3, 3, 1, 5, 2} //returns 3
d := []int{1, 1, 2, 2, 1}  //returns 1

fmt.Println(firstDuplicate(c))

fmt.Println(firstDuplicate(d))	
}

更多关于Golang中如何避免使用嵌套循环？的实战教程也可以访问 https://www.itying.com/category-94-b0.html

3 回复

哇！感谢如此快速而精彩的回复！我也很感谢对结构体部分的解释，我觉得我以前从未见过这样的用法。

更多关于Golang中如何避免使用嵌套循环？的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


可以使用映射（map）来实现对已见值的常数时间查找。

package main

import "fmt"

func hasDupe(in []int) bool {
    seen := make(map[int]struct{})
    for _, v := range in {
        if _, ok := seen[v]; ok {
            return true
        }
        seen[v] = struct{}{}
    }
    return false
}

func main() {
    fmt.Println(hasDupe([]int{1, 2, 3, 4, 2}))
    fmt.Println(hasDupe([]int{1, 2, 3, 4, 5}))
}

考虑到我们只需要跟踪整数类型，我相信还有更高效的数据结构可以使用。但映射（map）这种方式简单且是语言内置功能。

（struct{}这种特殊用法是零大小类型，因为我们只需要一个映射来记录某个值是否存在，而不需要记录该值具体是什么。）

在Go语言中，避免嵌套循环是提高性能的常见优化策略。对于查找数组中第一个重复元素的问题，可以使用哈希表（在Go中是map）来替代嵌套循环，将时间复杂度从O(n²)降低到O(n)。

以下是优化后的代码：

package main

import (
	"fmt"
)

func firstDuplicate(a []int) int {
    seen := make(map[int]bool)
    
    for _, val := range a {
        if seen[val] {
            return val
        }
        seen[val] = true
    }
    
    return -1
}

func main() {
    c := []int{2, 3, 3, 1, 5, 2} // 返回 3
    d := []int{1, 1, 2, 2, 1}    // 返回 1

    fmt.Println(firstDuplicate(c)) // 输出: 3
    fmt.Println(firstDuplicate(d)) // 输出: 1
}

这个实现使用map来记录已经出现过的元素。遍历数组时，对于每个元素：

  • 如果该元素已经在map中存在（值为true），则立即返回该元素
  • 否则将该元素添加到map中

这种方法只需要一次遍历，时间复杂度为O(n)，空间复杂度为O(n)，能够显著提升执行效率，轻松满足4秒的时间限制。

回到顶部