Here is my desired outcome
slice1 := []string{"foo", "bar","hello"}
slice2 := []string{"foo", "bar"}
difference(slice1, slice2)
=> ["hello"]
I am looking for the difference between the two string slices!
问问题
52569 次
9 回答
65
Assuming Go maps are ~O(1), here is an ~O(n) difference function that works on unsorted slices.
// difference returns the elements in `a` that aren't in `b`.
func difference(a, b []string) []string {
mb := make(map[string]struct{}, len(b))
for _, x := range b {
mb[x] = struct{}{}
}
var diff []string
for _, x := range a {
if _, found := mb[x]; !found {
diff = append(diff, x)
}
}
return diff
}
于 2017-08-01T02:31:23.663 回答
24
Depending on the size of the slices, different solutions might be best.
My answer assumes order doesn't matter.
Using simple loops, only to be used with smaller slices:
package main
import "fmt"
func difference(slice1 []string, slice2 []string) []string {
var diff []string
// Loop two times, first to find slice1 strings not in slice2,
// second loop to find slice2 strings not in slice1
for i := 0; i < 2; i++ {
for _, s1 := range slice1 {
found := false
for _, s2 := range slice2 {
if s1 == s2 {
found = true
break
}
}
// String not found. We add it to return slice
if !found {
diff = append(diff, s1)
}
}
// Swap the slices, only if it was the first loop
if i == 0 {
slice1, slice2 = slice2, slice1
}
}
return diff
}
func main() {
slice1 := []string{"foo", "bar", "hello"}
slice2 := []string{"foo", "world", "bar", "foo"}
fmt.Printf("%+v\n", difference(slice1, slice2))
}
Output:
[hello world]
Playground: http://play.golang.org/p/KHTmJcR4rg
于 2013-10-15T06:48:24.693 回答
15
I use the map to solve this problem
package main
import "fmt"
func main() {
slice1 := []string{"foo", "bar","hello"}
slice2 := []string{"foo", "bar","world"}
diffStr := difference(slice1, slice2)
for _, diffVal := range diffStr {
fmt.Println(diffVal)
}
}
func difference(slice1 []string, slice2 []string) ([]string){
diffStr := []string{}
m :=map [string]int{}
for _, s1Val := range slice1 {
m[s1Val] = 1
}
for _, s2Val := range slice2 {
m[s2Val] = m[s2Val] + 1
}
for mKey, mVal := range m {
if mVal==1 {
diffStr = append(diffStr, mKey)
}
}
return diffStr
}
output:
hello
world
于 2013-10-16T09:59:23.080 回答
2
func unique(slice []string) []string {
encountered := map[string]int{}
diff := []string{}
for _, v := range slice {
encountered[v] = encountered[v]+1
}
for _, v := range slice {
if encountered[v] == 1 {
diff = append(diff, v)
}
}
return diff
}
func main() {
slice1 := []string{"hello", "michael", "dorner"}
slice2 := []string{"hello", "michael"}
slice3 := []string{}
fmt.Println(unique(append(slice1, slice2...))) // [dorner]
fmt.Println(unique(append(slice2, slice3...))) // [michael michael]
}
于 2017-08-24T14:43:28.110 回答
2
func diff(a, b []string) []string {
temp := map[string]int{}
for _, s := range a {
temp[s]++
}
for _, s := range b {
temp[s]--
}
var result []string
for s, v := range temp {
if v != 0 {
result = append(result, s)
}
}
return result
}
If you want to handle duplicated strings, the v in the map can do that. And you can pick a.Remove(b) ( v>0 ) or b.Remove(a) (v<0)
于 2019-05-30T11:17:09.673 回答
1
As mentioned by ANisus, different approaches will suit different sizes of input slices. This solution will work in linear time O(n) independent of input size, but assumes that the "equality" includes index position.
Thus, in the OP's examples of:
slice1 := []string{"foo", "bar","hello"}
slice2 := []string{"foo", "bar"}
The entries foo and bar are equal not just due to value, but also due to their index in the slice.
Given these conditions, you can do something like:
package main
import "fmt"
func difference(s1, s2 []string) string {
var (
lenMin int
longest []string
out string
)
// Determine the shortest length and the longest slice
if len(s1) < len(s2) {
lenMin = len(s1)
longest = s2
} else {
lenMin = len(s2)
longest = s1
}
// compare common indeces
for i := 0; i < lenMin; i++ {
if s1[i] != s2[i] {
out += fmt.Sprintf("=>\t%s\t%s\n", s1[i], s2[i])
}
}
// add indeces not in common
for _, v := range longest[lenMin:] {
out += fmt.Sprintf("=>\t%s\n", v)
}
return out
}
func main() {
slice1 := []string{"foo", "bar", "hello"}
slice2 := []string{"foo", "bar"}
fmt.Print(difference(slice1, slice2))
}
Produces:
=> hello
If you change the slices to be:
func main() {
slice1 := []string{"foo", "baz", "hello"}
slice2 := []string{"foo", "bar"}
fmt.Print(difference(slice1, slice2))
}
It will produce:
=> baz bar
=> hello
于 2013-10-15T06:39:33.657 回答
1
Most of the other solutions here will fail to return the correct answer in case the slices contain duplicated elements.
This solution is O(n) time and O(n) space if the slices are already sorted, and O(n*log(n)) time O(n) space if they are not, but has the nice property of actually being correct.
func diff(a, b []string) []string {
a = sortIfNeeded(a)
b = sortIfNeeded(b)
var d []string
i, j := 0, 0
for i < len(a) && j < len(b) {
c := strings.Compare(a[i], b[j])
if c == 0 {
i++
j++
} else if c < 0 {
d = append(d, a[i])
i++
} else {
d = append(d, b[j])
j++
}
}
d = append(d, a[i:len(a)]...)
d = append(d, b[j:len(b)]...)
return d
}
func sortIfNeeded(a []string) []string {
if sort.StringsAreSorted(a) {
return a
}
s := append(a[:0:0], a...)
sort.Strings(s)
return s
}
If you know for sure that the slices are already sorted, you can remove the calls to sortIfNeeded (the reason for the defensive slice copy in sortIfNeeded is because sorting is done in-place, so we would be modifying the slices that are passed to diff).
See https://play.golang.org/p/lH-5L0aL1qr for tests showing correctness in face of duplicated entries.
于 2019-05-16T10:09:48.387 回答
0
I have this example but it works only for the elements of the first array "not present" in the second array
with generics
type HandleDiff[T comparable] func(item1 T, item2 T) bool
func HandleDiffDefault[T comparable](val1 T, val2 T) bool {
return val1 == val2
}
func Diff[T comparable](items1 []T, items2 []T, callback HandleDiff[T]) []T {
acc := []T{}
for _, item1 := range items1 {
find := false
for _, item2 := range items2 {
if callback(item1, item2) {
find = true
break
}
}
if !find {
acc = append(acc, item1)
}
}
return acc
}
usage
diff := Diff(items1, items2, HandleDiffDefault[string])
于 2022-02-26T14:55:39.637 回答
-1
The code below gives the absolute difference between strings regardless of the order. Space complexity O(n) and Time complexity O(n).
// difference returns the elements in a that aren't in b
func difference(a, b string) string {
longest, shortest := longestString(&a, &b)
var builder strings.Builder
var mem = make(map[rune]bool)
for _, s := range longest {
mem[s] = true
}
for _, s := range shortest {
if _, ok := mem[s]; ok {
mem[s] = false
}
}
for k, v := range mem {
if v == true {
builder.WriteRune(k)
}
}
return builder.String()
}
func longestString(a *string, b *string) ([]rune, []rune) {
if len(*a) > len(*b) {
return []rune(*a), []rune(*b)
}
return []rune(*b), []rune(*a)
}
于 2019-03-17T16:41:13.540 回答