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

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

0 голосов
/ 10 мая 2018

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

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 с.

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

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

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

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

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

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

Ответы [ 2 ]

0 голосов
/ 10 мая 2018

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

До 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 доступными для типов, которые включают хранимые свойства этих типов.
0 голосов
/ 10 мая 2018

Это место, где рекурсия решит проблему.Рассматривали ли вы рекурсию?Я собирался ответить на вопрос с реальным кодом, но я не знаю синтаксис для 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 () этого массива (который, в свою очередь, будет искать дубликаты, если он не найдет другой массив, а затем снова вызовет сам себя).

...