关于golang:Golang-高效的原地数组去重

43次阅读

共计 661 个字符，预计需要花费 2 分钟才能阅读完成。

应用 struct{} 节俭空间，指定 cap=len(arr) 防止 map 扩容。记录非反复元素索引 j，将元素前移，原地去重，只需一遍遍历。

工夫复杂度：O(n)
空间复杂度：O(n)

func removeDuplication_map(arr []string) []string {set := make(map[string]struct{}, len(arr))
    j := 0
    for _, v := range arr {_, ok := set[v]
        if ok {continue}
        set[v] = struct{}{}
        arr[j] = v
        j++
    }

    return arr[:j]
}

工夫复杂度：O(n)
空间复杂度：O(1)

func removeDuplication_sort(arr []string) []string {length := len(arr)
    if length == 0 {return arr}

    j := 0
    for i := 1; i < length; i++ {if arr[i] != arr[j] {
            j++
            if j < i {swap(arr, i, j)
            }
        }
    }

    return arr[:j+1]
}

func swap(arr []string, a, b int) {arr[a], arr[b] = arr[b], arr[a]
}

残缺代码及测试：https://github.com/win5do/pla…

Idiomatic way to remove duplicates in a slice : golang (reddit.com)

SliceTricks · golang/go Wiki (github.com)

正文完