Data Structures Array Problem: Cannot find the first repeating item-CodePudding

I am new to data structures and algorithms and I have a problem.

we have two arrays and I want to return first repeating item: eg: arr1 = [1, 2, 3, 4, 5] arr2 = [6, 2, 3, 1, 8]

in the above case first repeating item is 2.

This is the solution if we use hash table:

def find_same_hash(arr1, arr2):
    dictitonary = dict()
    for i in range(len(arr1)):
        dictitonary[arr1[i]] = i
    for j in range(len(arr2)):
        if array2[j] in dictitonary:
            return arr2[j]
        else:
            dictitonary[arr2[j]] = j
    return "Undefined"

result = find_same_hash(arr1, arr2)
print(result)

But what I need is the solution in Array: And this is what I am doing:

def find_same(arr1, arr2):
    for i in range(len(arr2)):
        for j in range(len(arr2)):
            if arr1[i] == arr2[j]:
                return arr1[i]
    return None

result = find_same(arr1, arr2)
print(result)

But the problem is that it is returning 1. 1 is repeating but it is not the first one to repeat.

CodePudding user response：

You need to reverse the order of the lists for iteration. That way you find the first (or 'earliest') item in arr2 that appears in arr1, not the opposite:

arr1 = [1, 2, 3, 4, 5]
arr2 = [6, 2, 3, 1, 8]

def find_same(arr1, arr2):
    for i in arr2:
      for j in arr1:
        if i == j:
          return i
    return None

print(find_same(arr1, arr2))
# 2

CodePudding user response：

Your specific problem is that you're checking them in the wrong order

def find_same(arr1, arr2):
    for i in range(len(arr2)):
        for j in range(len(arr1)):
            if arr1[j] == arr2[i]:
                return arr1[i]
    return None

result = find_same(arr1, arr2)
print(result)

There's a simpler option..

list1 = [1, 2, 3, 4, 5]
list2 = [6, 2, 3, 1, 8]

def first_duplicate(list1,list2):
    for n in list2:
        if n in list1:
            return n

Using a generator is very neat and tidy:

print(next(n for n in list2 if n in list1))