Создать срез из дублирующих элементов двух срезов - PullRequest
Новая
       6

Создать срез из дублирующих элементов двух срезов

0 голосов
/ 28 июня 2018

У меня есть два ломтика: 

slice1 := []string{"a", "b", "c", "d"}
slice2 := []string{"c", "d", "e", "f"}

Ожидаемый результат: 

[]string{"c", "d"}

Каков наилучший способ создания фрагмента из дубликатов slice1 и slice2 со следующими характеристиками:

  1. Минимальный код
  2. Ломтики большие
  3. Ломтики не отсортированы
  4. Не изменять ломтики
  5. Они не могут содержать дубликаты

Вот что я пробовал: 

slice1 := []string{"a", "b", "c", "d"}
slice2 := []string{"c", "d", "e", "f"}
duplicateItems := []string{}
for _, item1 := range slice1 {
    for _, item2 := range slice2 {
        if item1 == item2 {
            duplicateItems = append(duplicateItems, item1)
        }
    }
}

fmt.Println(duplicateItems) // [c d]

1 Ответ

0 голосов
/ 28 июня 2018

Этот метод жертвует использованием памяти для большой сложности O (скорость). 

// flatten the first slice into a map for O(1) constant time lookup
m1 := make(map[string]struct{})
for _, v := range slice1 {
    m1[v] = struct{}{}
}

var dup []string

// iterate slice 2, using the O(1) lookup.
for _, v := range slice2 {
    if _, exists := m1[v]; exists {
        dup = append(dup, v)
    }
}

// dup contains the duplicates

Вы посещаете каждый из элементов только один раз, но требования к памяти намного больше, поскольку slice1 необходимо сохранить на карте.

Вы могли бы расширить этот код, чтобы сгладить на карте наименьший из 2 фрагментов, чтобы уменьшить требования к памяти.

стоит отметить, что вместо map[string]bool используется map[string]struct{}, поскольку struct{} использует ноль байтов памяти

...