Logo

Programming-Idioms

History of Idiom 119 > diff from v39 to v40

Edit summary for version 40 by programming-idioms.org:
[Go] Big-O
↷

Version 39

2018-04-11, 21:32:59

Version 40

2018-04-11, 21:34:44

Idiom #119 Deduplicate list

Remove duplicates from list x.
Explain if original order is preserved.

Illustration

Idiom #119 Deduplicate list

Remove duplicates from list x.
Explain if original order is preserved.

Illustration
Extra Keywords
deduplicate dupe dupes redundant redundancy
Extra Keywords
deduplicate dupe dupes redundant redundancy
Code 
y := make(map[T]struct{}, len(x))
for _, v := range x {
	y[v] = struct{}{}
}
x2 := make([]T, 0, len(y))
for _, v := range x {
	if _, ok := y[v]; ok {
		x2 = append(x2, v)
		delete(y, v)
	}
}
x = x2
Code 
y := make(map[T]struct{}, len(x))
for _, v := range x {
	y[v] = struct{}{}
}
x2 := make([]T, 0, len(y))
for _, v := range x {
	if _, ok := y[v]; ok {
		x2 = append(x2, v)
		delete(y, v)
	}
}
x = x2
Comments bubble
T is the type of the items.
Iterate twice, from list to map, then from map to list.
Original order is preserved.
Comments bubble
Original order is preserved.
T is the type of the items.
Iterate twice, from list to map, then from map to list.

This is O(n).
Demo URL
https://play.golang.org/p/fBANh9c8_Ux
Demo URL
https://play.golang.org/p/fBANh9c8_Ux