python algorithm - quickly find two numbers that meet the conditions-Python Tutorial-php.cn

python algorithm - quickly find two numbers that meet the conditions

高洛峰

Release： 2016-10-18 10:38:23

Original

2187 people have browsed it

The premise of the question is that there must be such two numbers

I won’t write down the solution one... You can’t think of it usually

At first, I thought of using a hash table at the end of solution two

(Actually, I thought of creating a hash table as big as the target Array... If it exists, write it into the index, but if you want to find them all, you have to have a two-dimensional array. But then I thought if the target is very large, it will be a waste of space... So I changed it to Dict)

I later found out the problem Just ask for two numbers - -

Expansion questions are more interesting

It shouldn’t be difficult to find three. The others are not clear yet. If you want to add more...

1. Two-dimensional array

def find_pair(A, target):
    B = [[] for i in range(target + 1)]
    for i in range(0, len(A)):
        if A[i] <= target:
            B[A[i]].append(i)
    for i in range(0, target / 2 + 1):
        if len(B[i]) != 0 and len(B[target - i]) != 0:
            print(i, B[i], target-i, B[target-i])
  
if __name__ == "__main__":
    A = [0, 1, 1, 2, 11, 8, 3, 4, 5, 6, 7, 8, 9, 10]
    find_pair(A, 9)

Copy after login

2. Dictionary

def find_pair(A, target):
    B = {}
    for i in range(0, len(A)):
        if A[i] <= target:
            if not B.has_key(A[i]):
                B[A[i]] = [i]
            else:
                B[A[i]].append(i)
    for i in range(0, target / 2 + 1):
        if B.has_key(i) and B.has_key(target-i):
            print(i, B[i], target-i, B[target-i])
  
if __name__ == "__main__":
    A = [0, 1, 1, 2, 11, 8, 3, 4, 5, 6, 7, 8, 9, 10]
    find_pair(A, 9)

Copy after login

3. This method has been reordered. I don’t know what the meaning of returning the index in the book is... I’m lazy and just use the built-in one...

def find_pair(A, target):
    A.sort()
    i, j = 0, len(A) - 1
    while i < j:
        s = A[i] + A[j]
        if s == target:
            print(i, A[i], j, A[j])
            i += 1
            j -= 1
        elif s < target:
            i += 1
        else:
            j -= 1
  
if __name__ == "__main__":
    A = [0, 1, 1, 2, 11, 8, 3, 4, 5, 6, 7, 8, 9, 10]
    find_pair(A, 9)

Copy after login