skip to Main Content

I dont know how doint that. I try find replacement obj method
indexOfObject on the swift but not find

i have array = [1,3,6,2,3] and input in array value 3, i am need find repeating value with min index from array. Answer with index 1. How do it?

3

Answers


  1. Assume you have an array of n integers, with a[i] = i, except that a[1] = a[2] = 1, and I may or may not have have changed a[i] = 0 for some i >= 2.

    The smallest index of a duplicate element is either 0 or 1. To find out which you have to find the i >= 2 with a[i] = 0 or find that no such i exists. So you have to visit all array elements.

    Login or Signup to reply.
  2. You have to loop through the entire collection, for each item, see if we had seen this before. And as we are doing that, let’s keep track of the index of the first item that has been repeated somewhere in the collection, to see if this is the first repeated item or not:

    extension Collection where Element: Hashable {
        func indexOfFirstRepeated() -> Index? {
            var result: Index?                                         // the index of the first item repeated anywhere else in the collection
            var firstOccurrences: [Element: Index] = [:]               // dictionary to keep track of the first item that every element was first encountered in the collection
            
            for (index, element) in zip(indices, self) {
                if let firstOccurrence = firstOccurrences[element] {   // find previous occurrence of this value, if any
                    if let previousLowestIndex = result {              // if we found this element before, let's see if we had already found another repeated element
                        if firstOccurrence < previousLowestIndex {     // if so, let’s see if the first occurrence of this element occurred before the first occurrence of the previously discovered repeated element
                            result = firstOccurrence
                        }
                    } else {                                           // otherwise, no prior repeated element found, so this is our first repeated element found thus far
                        result = firstOccurrence
                    }
                } else {
                    firstOccurrences[element] = index                  // if we got here, this is the first time we've seen this element, so record the index of this first occurrence
                }
            }
            
            return result
        }
    }
    

    Thus:

    let array = [9,8,7,1,3,6,2,3,1]
    if let index = array.indexOfFirstRepeated() {
        print(index)                                                   // 3
    }
    

    Now, obviously, as we iterate through this array, the value 3 is the first value that we will see repeated, but that doesn’t matter, because the repeated value 1 will be found at the very end of the array, and 1’s first index is lower than 3’s first index.


    Two observations on the above:

    1. I made it generic, so that it works on any hashable type, e.g.:

      let array = ["bill", "sam", "susan", "sam", "bill"]
      if let index = array.indexOfFirstRepeated() {
          print(index)
      } else {
          print("not found")
      }
      
    2. I made this a Collection extension (rather than an Array extension) so that it would work on other collection types (e.g. array slices, etc.). You can make it an Array extension, just as easily, but we prefer to use the most abstract type that is convenient, to make it as flexible as possible.

    Login or Signup to reply.
  3. This is basically a riff on uniqued.

    import Algorithms
    
    public extension BidirectionalCollection where Element: Hashable {
      var firstDuplicate: (index: Index, element: Element)? {
        var set: Set<Element> = []
        return indexed().reversed().reduce(into: nil) {
          if !set.insert($1.element).inserted {
            $0 = $1
          }
        }
      }
    }
    

    You can get the last duplicate by not reversing before reducing.

    Login or Signup to reply.
Please signup or login to give your own answer.
Back To Top
Search