如何从阵列中删除重复项

Question

说我有一个字符串数组:

let arrayOfStrings = ["a", "b", "a", "c", "a", "d"]

我怎么能摆脱重复？

Answer 1

您可以使用数组函数contains(_:)来检查元素是否已经是数组的一部分,但这相当慢,而对于大型数组,它将无法很好地执行.^(1.)最好将条目复制到a Set并使用Set操作来查找和删除重复项.集合经过优化,可快速测试集合成员资格,因此if aSet.contains(item)速度要快得多if anArray.contains(item).

如果您不关心保留项目的顺序,只需将数组复制到一个集合中,然后再复制到数组中即可.但是,这确实意味着结果数组中的项目将按不同的顺序排列.

在保留顺序的同时从字符串数组中删除重复项的函数可能如下所示:

func uniqueElementsFrom(array: [String]) -> [String] {
  //Create an empty Set to track unique items
  var set = Set<String>()
  let result = array.filter {
    guard !set.contains($0) else {
      //If the set already contains this object, return false
      //so we skip it
      return false
    }
    //Add this item to the set since it will now be in the array
    set.insert($0)
    //Return true so that filtered array will contain this item.
    return true
  }
  return result
}

如果你用这样的代码调用它:

let arrayOfStrings = ["a", "b", "a", "c", "a", "d"]
let uniqueStrings = uniqueElementsFrom(array:arrayOfStrings)
print("Unique elements from \(arrayOfStrings) = \n” + 
  “\(uniqueStrings)")

输出将是

来自["a","b","a","c","a","d"]的独特元素=

["A B C D"]

但是,该函数仅适用于字符串数组.如果我们能编写一个可以从任何类型的数组中删除重复项的函数,那将是一件好事.

这是Generics的工作.但是有一个问题.集合只能包含符合Hashable协议的对象,因为集合使用哈希来更快地测试集合成员资格.

我们可以使用Generics 重写uniqueElementsFrom(array:)函数以获取符合Hashable协议的任何数组.该代码如下所示:

func uniqueElementsFrom<T: Hashable>(array: [T]) -> [T] {
  var set = Set<T>()
  let result = array.filter {
    guard !set.contains($0) else {
      return false
    }
    set.insert($0)
    return true
  }
  return result
}

该<T: Hashable>函数名后位说"这个函数的其余部分将引用一个类型T是不确定的.可以肯定的唯一的事情是,类型T将符合哈希的协议."

这种形式的uniqueElementsFrom(array:)函数适用于任何元素的数组Hashable.

^(1.)对于数组,contains(_:)具有O(n)性能,并且循环遍历数组,测试数组以查看它是否包含contains(_:)具有几乎所有性能的新元素O(n^2),这对于除小数组之外的任何事物确实非常糟糕.我很确定它Set的contains(_:)功能具有恒定的时间性能,所以整个过程都会有O(n)性能.