Удалить дубликаты из многомерного массива

Я написал следующее расширение, чтобы удалить дубликаты из моего массива.

extension Array where Element : Equatable{

    func removeDups() -> [Element]{
        var result = [Element]()

        for element in self{
            if !result.contains(element){
                result.append(element)
            }
        }

        return result
    }
}

Линейный массив

let linearArr = [1,2,2,3]
linearArr.removeDups() // [1,2,3] works well!

Многомерный массив

let multiDimArr : [[Int]] = [[1,2,3], [1,2,3], [1,2 ,4]]
multiDimArr.removeDups() // Error!

Тип [Int] не соответствует Equatable

Я читаю здесь. И ответ говорит, что сравнение массивов с помощью == должно сработать. Это не работает все время:

Работает

if (["1", "2"] == ["1", "2"]){
    print("true")
}

Не работает

if ([1, 2] == [1, 2]){ // ERROR!
    print("true")
}

Неоднозначное использование оператора '=='

Это своеобразно. Я могу сравнить массив String но не могу сравнить массив Int s.

Я также видел этот комментарий:

Причина myArray1 == myArray2 в том, что NSObject соответствует Equatable, вызывая -[equals:] провести тест

Не уверен, что комментарий still остается в силе.

Подвести итоги:

  • Равномерны ли массивы? Могу ли я сравнить их, используя ==
  • Чем отличается массив для сравнения String S против Массив Int s
  • Как я могу удалить дубликаты из многомерного массива?

Я сейчас работаю с Swift 4.0.2

Источник

2 ответа

Решение

Равномерны ли массивы? Могу ли я сравнить их, используя ==

До Swift 4.1, Array не соответствовал Equatable, Однако была перегрузка == который сравнил два массива с Equatable элементы, что позволило компилировать это:

if ["1", "2"] == ["1", "2"] { // using <T : Equatable>(lhs: [T], rhs: [T]) -> Bool
    print("true")
}

Однако в Swift 4.1 (доступно с Xcode 9.3), Array<Element> теперь соответствует Equatable когда это Element соответствует Equatable, Это изменение дано в журнале изменений:

Swift 4.1

[...]

  • SE-0143 Стандартные типы библиотек Optional, Array, ArraySlice, ContiguousArray, а также Dictionary теперь соответствуют Equatable протокол, когда их типы элементов соответствуют Equatable, Это позволяет == оператор для составления (например, можно сравнить два значения типа [Int : [Int?]?] с ==), а также использовать различные алгоритмы, определенные для Equatable типы элементов, такие как index(of:),

Ваш пример с multiDimArr.removeDups() компилируется и запускается как положено в 4.1, давая результат [[1, 2, 3], [1, 2, 4]],

В Swift 4.0.3 вы можете взломать его, добавив еще одну перегрузку removeDups() для вложенных массивов:

extension Array {
  func removeDups<T : Equatable>() -> [Element] where Element == [T] {

    var result = [Element]()

    for element in self{
      if !result.contains(where: { element == $0 }) {
        result.append(element)
      }
    }

    return result
  }
}

let multiDimArr = [[1, 2, 3], [1, 2, 3], [1, 2, 4]]
print(multiDimArr.removeDups()) // [[1, 2, 3], [1, 2, 4]]

К сожалению, это приводит к некоторому дублированию кода, но, по крайней мере, вы сможете избавиться от него при обновлении до 4.1.

Тот факт, что этот пример не компилируется ни в 4.0.3, ни в 4.1:

if [1, 2] == [1, 2] { // error: Ambiguous use of operator '=='
    print("true")
}

из-за ошибки SR-5944 - компилятор считает, что это неоднозначно из-за == перегрузки для IndexSet а также IndexPath (оба из которых ExpressibleByArrayLiteral). Но Swift должен по умолчанию использовать литерал массива Array хотя, разрешая неоднозначность.

Сказать либо:

if [1, 2] as [Int] == [1, 2] {
    print("true")
}

или не импортировать Foundation решает проблему.

Наконец, стоит отметить, что производительность removeDups() может быть улучшено, если Element тип также Hashable, позволяя ему работать в линейном, а не квадратичном времени:

extension Array where Element : Hashable {

  func removeDups() -> [Element] {
    var uniquedElements = Set<Element>()
    return filter { uniquedElements.insert($0).inserted }
  }
}

Здесь мы используем набор для хранения элементов, которые мы видели, исключая любые, которые мы уже вставили в него. Это также позволяет нам использовать filter(_:), как отмечает @Alexander.

И в Swift 4.2, Array также условно соответствует Hashable когда это Element является Hashable:

Swift 4.2

[...]

  • SE-0143 Стандартные типы библиотек Optional, Array, ArraySlice, ContiguousArray, Dictionary, DictionaryLiteral, Range, а также ClosedRange теперь соответствуют Hashable протокол, когда их элемент или связанные типы (в зависимости от обстоятельств) соответствуют Hashable, Это делает синтезированный Hashable реализации доступны для типов, которые включают хранимые свойства этих типов.
Источник

Это место, где рекурсия решит проблему. Рассматривали ли вы рекурсию? Я собирался ответить на вопрос с реальным кодом, но я не знаю синтаксис для Swift. Итак, вот некоторый песудокод:

function removeDupes() {
    buffer = array;
    foreach this->elements as key => element {             
         if(element is type array) {
              this->elements[key] = element->removeDupes();
         } else {
              if(!this->contains(element)) {
                  buffer->add(element);
              }
         }             
    }
    return buffer;
}

По сути, вы хотите проверить, является ли сам элемент массивом. Если это так, то вы хотите вызвать метод removeDupes() этого массива (который, в свою очередь, будет искать дубликаты, если только он не найдет другой массив, он снова вызовет сам себя).

Источник
Другие вопросы по тегам