CODEWITHSUNDEEP
arraysswiftios8addressbook
C0mrade
C0mrade

Reputation: 1245

Find Duplicate Elements In Array Using Swift

How to find Duplicate Elements in Array? I have array of phone numbers so in the phone numbers i should start searching from the right side to the left side and find similar 6 integers. then i should print them out.

Upvotes: 60

Views: 76453

Answers (17)

Rob Caraway
Rob Caraway

Reputation: 3926

Swift 4+

One line, fast solution:

var numbers = [1,2,3,4,5,6,6,6,7,8,8]
let dups = Dictionary(grouping: numbers, by: {$0}).filter { $1.count > 1 }.keys

//Results: [6, 8]

Upvotes: 40

Irfan Gul
Irfan Gul

Reputation: 1577

Simple solution:

let numbers = ["1","2","3","6","8","3","6","3","5","8","9","7"]

func findDuplicate(list: [String]) -> [String] {
    var duplicates = Set<String>()
    for element in list {
        if list.firstIndex(of: element) != list.lastIndex(of: element) {
            duplicates.insert(element)
        }
    }
    
    return duplicates.sorted()
}

Upvotes: 0

Rob
Rob

Reputation: 437592

To find duplicates, you could build cross reference by phone number, then filter that down to duplicates only. For example, consider:

let contacts = [
    Contact(name: "Rob",     phone: "555-1111"),
    Contact(name: "Richard", phone: "555-2222"),
    Contact(name: "Rachel",  phone: "555-1111"),
    Contact(name: "Loren",   phone: "555-2222"),
    Contact(name: "Mary",    phone: "555-3333"),
    Contact(name: "Susie",   phone: "555-2222")
]

You can build the cross reference dictionary with:

let crossReference = Dictionary(grouping: contacts, by: \.phone)

Then, to find the duplicates:

let duplicates = crossReference
    .filter { $1.count > 1 }

Clearly use whatever model types make sense for you, but the above uses the following Contact type:

struct Contact {
    let name: String
    let phone: String
}

There are many, many ways to implement this, so I would not focus on the implementation details above, but rather focus on the concept: Build cross reference original array by some key (e.g. phone number) and then filter results down to just those keys with duplicate values.

It sounds like you want to flatten this structure that reflects the duplicates, into a single array of contacts (I'm not sure why you'd want to do that, as you lose the structure identifying which are duplicates of each other), but if you want to do that, you can flatMap it:

let flattenedDuplicates = crossReference
    .filter { $1.count > 1 }                 // filter down to only those with multiple contacts
    .flatMap { $0.1 }                        // flatten it down to just array of contacts that are duplicates of something else

Upvotes: 69

user652038
user652038

Reputation:

There's still quite a bit of useful reusable stuff missing from Swift to make this simple, but OrderedCollections, which have not been used by the other answers yet, make it easier to get the duplicates "in order".

XCTAssertEqual(
  .init("💞❤️‍🔥💝❤️‍🔥🫀💕💔❤️‍🔥💕💝💘".duplicates),
  "❤️‍🔥💝💕"
)

import OrderedCollections

public extension Sequence where Element: Hashable {
  /// The non-unique elements of this collection, in the order of their first occurrences.
  var duplicates: OrderedSet<Element> {
    OrderedDictionary(bucketing: self).filter { $1 > 1 }.keys
  }
}

import struct OrderedCollections.OrderedDictionary

public protocol DictionaryProtocol {
  associatedtype Key
  associatedtype Value

  init<KeysAndValues: Sequence>(
    _: KeysAndValues,
    uniquingKeysWith: (Value, Value) throws -> Value
  ) rethrows where KeysAndValues.Element == (Key, Value)
}

extension Dictionary: DictionaryProtocol { }
extension OrderedDictionary: DictionaryProtocol { }

public extension DictionaryProtocol where Value == Int {
  /// Create "buckets" from a sequence of keys,
  /// such as might be used for a histogram.
  init<Keys: Sequence>(bucketing unbucketedKeys: Keys)
  where Keys.Element == Key {
    self.init(zip(unbucketedKeys, 1), uniquingKeysWith: +)
  }
}

/// `zip` a sequence with a single value, instead of another sequence.
@inlinable public func zip<Sequence: Swift.Sequence, Constant>(
  _ sequence: Sequence, _ constant: Constant
) -> LazyMapSequence<
  LazySequence<Sequence>.Elements,
  (LazySequence<Sequence>.Element, Constant)
> {
 sequence.lazy.map { ($0, constant) }
}

Upvotes: 1

thecoolwinter
thecoolwinter

Reputation: 1010

Here's an efficient, O(n) method to do it. Some of the other answers here use .filter on a duplicates array or even the return value array, which makes the operation work in O(n^2) (using .contains is the same). Using a Set to store the duplicates we can make it O(n).

The other method that's been shown here is using a dictionary to first store the array elements. The idea being that a dictionary can't have duplicate elements. However, this doesn't guarantee the original order of the array to be preserved, so we need a different method.

Here's an Array extension that adds a removeDuplicates method that is efficient and guarantees the same result order as the original array's order.

extension Array where Iterator.Element == Int {
    func removeDuplicates() -> [Int] {
        var retVal: [Int] = []
        var duplicates: Set<Int> = []
        
        for number in self {
            if !duplicates.contains(number) {
                duplicates.insert(number)
                retVal.append(number)
            }
        }
        
        return retVal
    }
}

If you want to return the duplicate elements, just reverse some of the checks in the for loop (Still O(n)).

extension Array where Iterator.Element == Int {
    func findDuplicates() -> [Int] {
        var retVal: [Int] = []
        var duplicates: Set<Int> = []
        
        for number in self {
            if duplicates.contains(number) {
                retVal.append(number)
            } else {
                duplicates.insert(number)
            }
        }
        
        return retVal
    }
}

Upvotes: 0

Eric Yuan
Eric Yuan

Reputation: 1492

I've found a way by using reduce, here is the code(Swift 4):

let testNumbers = [1,1,2,3,4,5,2]
let nondupicate = testNumbers.reduce(into: [Int]()) {
    if !$0.contains($1) {
        $0.append($1)
    } else {
        print("Found duplicate: \($1)")
    }
}

As a side effect, it returns an array with no duplicated elements.

You can easily modify it for counting duplicated elements numbers, checking string arrays etc.

Upvotes: 4

Shashank
Shashank

Reputation: 21

let inputArray = [9820213496, 9546533545, 9820213496, 995543567]
var outputArray = [Int]()
for element in inputArray{
    if outputArray.contains(element){
        print("\(element) is Duplicate")
    }else{
        outputArray.append(element)
    }
}
print(outputArray) // print Array without duplication

Upvotes: 2

parilogic
parilogic

Reputation: 1179

// find duplicate number in an array 
var arrNum = [1, 2, 3 , 3, 2, 5, 6, 2] 
let setOfNum = Set(Array(arrNum))
print(setOfNum)

Output: [6, 3, 5, 1, 2]

// find duplicate string in an array 
var arrStr = ["1", "2", "3" , "3", "2", "5", "6", "2"]  
let setOfStr = Set(Array(arrStr))
print(setOfNum)

Output: [6, 3, 5, 1, 2]

Upvotes: 0

Patrick Perini
Patrick Perini

Reputation: 22633

Feeling ~clever~. Given an array of Ints

let x = [1, 1, 2, 3, 4, 5, 5]
let duplicates = Array(Set(x.filter({ (i: Int) in x.filter({ $0 == i }).count > 1})))
// [1, 5]

Please note, this is horrendously inefficient for everyone involved, including the compiler, and you.

I'm just showing off.

Edit: lol someone downvoted this, which leads me to reiterate, just in case: please DO NOT USE THIS in production or anywhere else.

Upvotes: 56

Benjohn
Benjohn

Reputation: 13887

Entirely derived from Rob's very neat answer. I've made it in to an Array extension and given names to the intermediate steps for clarity:

extension Array where Element: Hashable {
    func duplicates() -> Array {
        let groups = Dictionary(grouping: self, by: {$0})
        let duplicateGroups = groups.filter {$1.count > 1}
        let duplicates = Array(duplicateGroups.keys)
        return duplicates
    }
}

[1, 2, 2, 3, 1].duplicates() -> [1, 2]

Upvotes: 15

miss Gbot
miss Gbot

Reputation: 373

extension Array where Element: Hashable {
     func similar() -> Self {
        var used = [Element: Bool]()

        return self.filter { used.updateValue(true, forKey: $0) != nil }
    }
}

Upvotes: -1

Maverick
Maverick

Reputation: 3259

Antoine's solution in Swift 3+ syntax

extension Array {

    func filterDuplicates(includeElement: @escaping (_ lhs: Element, _ rhs: Element) -> Bool) -> [Element] {

        var results = [Element]()

        forEach { (element) in

            let existingElements = results.filter {
                return includeElement(element, $0)
            }

            if existingElements.count == 0 {
                results.append(element)
            }
        }
        return results
    }
}

Upvotes: 1

Tora
Tora

Reputation: 1020

I also had a similar problem and have overcome in the following way. (Xcode 8.3.2)

let a = [123456, 234567, 345678, 123456, 456789, 135790, 456789, 142638]
var b = a // copy-on-write so that "a" won't be modified

while let c = b.popLast() {
  b.forEach() {
    if $0 == c {
      Swift.print("Duplication: \(c)")
    }
  }
}

//  Duplication: 456789
//  Duplication: 123456

The point is that the number of comparison. It would be smaller than others.

Assume that the number of items in the array is N. In each loop, the number will be decrementing by one. So, the total number will be (N-1) + (N-2) + (N-3) + ... + 2 + 1 = N * (N-1) / 2 When N = 10, that will be 9 + 8 + ... = 45

In contrast, that of some algorithms might be N * N. When N = 10 that will be 100.

In spite of that, taking into account of the cost of deep-copy or shallow-copy, I agree that @Patrick Perini's brilliant way would be better than this in some situations even the number of that would be N * N.

EDIT:

Alternative way with IteratorProtocol

let a = [123456, 234567, 345678, 123456, 456789, 135790, 456789, 142638]
var i = a.makeIterator()

while let c = i.next() {
  var j = i
  while let d = j.next() {
    if c == d {
      Swift.print("Duplication: \(c)")
    }
  }
}

//  Duplication: 123456
//  Duplication: 456789

That looks more complex, but uses the same idea as before. This does not have unnecessary memory allocations or copies.

My concern is efficiency, i.e. quicker UI response, longer battery life, smaller memory footprint, etc. Avoiding unnecessary memory allocations and/or memory copies which are automatically done by Swift in the behind scene would be crucial if we are providing competitive products. (-;

Upvotes: 0

Ryan Heitner
Ryan Heitner

Reputation: 13632

A very simple answer which preserves all duplicates 

let originalNums = [5, 3, 2, 3 , 7 , 5,3]
var nums = Array(originalNums)

let numSet = Set(nums)

for num in numSet {
  if let index = nums.index(of: num) {
     nums.remove(at: index)
  }
}

output

[3, 5, 3]

Upvotes: 0

Vlad
Vlad

Reputation: 6732

Same as in @tikhop's answer, but as Array extension (Swift 3):

extension Array where Element: Comparable & Hashable {

   public var duplicates: [Element] {

      let sortedElements = sorted { $0 < $1 }
      var duplicatedElements = Set<Element>()

      var previousElement: Element?
      for element in sortedElements {
         if previousElement == element {
            duplicatedElements.insert(element)
         }
         previousElement = element
      }

      return Array(duplicatedElements)
   }

}

Upvotes: 1

Antoine
Antoine

Reputation: 23986

To filter an array based on properties, you can use this method:

extension Array {

    func filterDuplicates(@noescape includeElement: (lhs:Element, rhs:Element) -> Bool) -> [Element]{
        var results = [Element]()

        forEach { (element) in
            let existingElements = results.filter {
                return includeElement(lhs: element, rhs: $0)
            }
            if existingElements.count == 0 {
                results.append(element)
            }
        }

        return results
    }
}

Which you can call as followed, based on the contacts example of Rob:

let filteredContacts = myContacts.filterDuplicates { $0.name == $1.name && $0.phone == $1.phone }

Upvotes: 6

tikhop
tikhop

Reputation: 2087

You could implement it using "Merge sort", but you need to make one modification, during the merge step you should ignore the duplicates.

The easiest way to find duplicate elements is if the phone number is just a 6-digit number and has type Int, you could sort the array of phone numbers and than filter that to find duplicates.

var phoneNumbers = [123456, 234567, 345678, 123456, 456789, 135790, 456789, 142638]

func findDuplicates(sortedArray array: [Int]) -> [Int]
{
    var duplicates: [Int] = []

    var prevItem: Int = 0
    var addedItem: Int = 0

    for item in array
    {
        if(prevItem == item && addedItem != item)
        {
            duplicates.append(item)
            addedItem = item
        }

        prevItem = item
    }

    return duplicates
}

func sortPhoneNumbers(phoneNumbers: [Int]) -> [Int]
{
    return phoneNumbers.sorted({ return $0<$1 })
}

sortPhoneNumbers(phoneNumbers)
findDuplicates(sortPhoneNumbers(phoneNumbers))

In addition, you could implement the findDuplicates method in different ways:

Using Set (Swift 1.2+):

func findDuplicates(array: [Int]) -> [Int]
{
    var duplicates = Set<Int>()
    var prevItem = 0       

    for item in array
    {
        if(prevItem == item)
        {
            duplicates.insert(item)
        }

        prevItem = item
    }

    return Array(duplicates)
}

And so on.

Upvotes: 7

Related Questions