Golang 高效的原地数组去重
文章目录
非排序数组
使用 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...
Reference
Idiomatic way to remove duplicates in a slice : golang (reddit.com)
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论