python演算法 - 快速找出滿足條件的兩個數

高洛峰
發布: 2016-10-18 10:38:23
原創
2165 人瀏覽過

題目前提是一定存在這樣兩個數

解法一就不寫了...一般想不到吧

一開始想到的是解法二最後的用hash表

(其實是想到創建一個跟target一樣大的數組啦..存在就寫入index,但是要全部找出,那得二維數組,但是後面想到target要是很大的話,是不是浪費空間了...所以改成Dict)

後面發現題目只要求給出兩個數就好了啊- -

擴展問題比較有意思

找三個應該不難,其它還不清楚,有想再補充...

1.二維數組

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)
登入後複製

2.字典

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)
登入後複製

3.這種方法都已經重新排序了,不知道書上還返回索引有什麼意義...排序偷懶直接用內置的啦...    

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)
登入後複製


來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板