find the minimum index of a repeating element in the array Swift-CodePudding

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?

CodePudding user response：

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.

CodePudding user response：

You can iterate through your array, saving the first index for each respective element, exiting as soon as you find an element has already been encountered. By storing these indices in a dictionary, each lookup is O(1), and the overall performance is O(n):

extension Array where Element: Hashable {
    func indexOfFirstRepeated() -> Index? {
        var lookup: [Element: Index] = [:]
        
        for (index, element) in enumerated() {
            if let firstIndex = lookup[element] {
                return firstIndex
            }
            
            lookup[element] = index
        }
        
        return nil
    }
}

Then

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

This has the virtue that it works with any array of hashable values, e.g.

let array = ["joe", "larry", "sam", "bill", "sam", "bill"] 
if let index = array.indexOfFirstRepeated() {
    print(index)                                            // 2
}

Or, as Leo pointed out, you can alternatively write this as an extension on Collection, and it is even more flexible (working on any collection, such as array slices or what have you, not just Array instances):

extension Collection where Element: Hashable {
    func indexOfFirstRepeated() -> Index? {
        var lookup: [Element: Index] = [:]
        
        for (index, element) in zip(indices, self) {
            if let firstIndex = lookup[element] {
                return firstIndex
            }
            
            lookup[element] = index
        }
        
        return nil
    }
}