leetcode349

输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]
  • 暴力解法
func intersection(nums1 []int, nums2 []int) []int {
    // 定义map 和 切片
    m := map[int]int{}
    mm := []int{}
    // 双层循环
    for _,v := range nums1{
        for _,vv :=range nums2{
            if v==vv{
                m[vv]++
            }
        }
    }
    for k,_:=range m{
        mm = append(mm, k)
    }
    return mm
}
  • hash
func intersection(nums1 []int, nums2 []int) []int {
    m := map[int]int{}

    for _,v:=range nums1{
        if m[v]==0{
            m[v]++
        }
    }
    for _,v:=range nums2{
        // 等于1,再加,这样重合元素最后为2
        if m[v]==1{
            m[v]++
        }
    }
    index := 0
    mm := []int{}

    for k,v := range m{
        if v==2{
            mm=append(mm, k)
            index++
        }
    }
    return mm
}


– hash优化

func intersection(nums1 []int, nums2 []int) []int {
    m := make(map[int]int)
    for _, v := range nums1 {
        m[v] = 1
    }
    var res []int
    // 利用判断该元素在数组,且count>0,实现重复值只拿一次放入返回结果中
    for _, v:=range nums2{
        if count,ok:=m[v];ok&&count>0{
            m[v]--
            res = append(res, v)
        }
    }
    return res
}

继续优化:

func intersection(nums1 []int, nums2 []int) []int {
    set:=make(map[int]struct{},0)
    res:=make([]int,0)
    for _,v:=range nums1{
        if _,ok:=set[v];!ok{
            set[v]=struct{}{}
        }
    }
    for _,v:=range nums2{
        //如果v,存在于上一个数组中,加入res,并清空该set值
        if _,ok:=set[v];ok{
            res=append(res,v)
            delete(set, v)
        }
    }
    return res
}
分类: 算法

站点统计

  • 文章总数:309 篇
  • 分类总数:19 个
  • 标签总数:190 个
  • 运行天数:975 天
  • 访问总数:72528 人次

浙公网安备33011302000604

辽ICP备20003309号