亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

解決 Python 中的“firstDuplicate”問題

解決 Python 中的“firstDuplicate”問題

慕尼黑5688855 2021-06-18 14:37:56
我正在嘗試解決來自 codesignal.com 的以下挑戰:給定一個只包含 1 到 a.length 范圍內的數字的數組 a,找到第一個重復的數字,該數字的第二次出現具有最小索引。換句話說,如果重復的數字超過 1 個,則返回第二次出現的索引比第二次出現的另一個數字小的數字。如果沒有這樣的元素,則返回 -1。例子For a = [2, 1, 3, 5, 3, 2],輸出應該是 firstDuplicate(a) = 3。有 2 個重復:數字 2 和 3。第二次出現 3 的索引比第二次出現的 2 小,所以答案是 3。對于a = [2, 4, 3, 5, 1],輸出應該是 firstDuplicate(a) = -1。執行時間限制為 4 秒。保證的約束是:1 ≤ a.length ≤ 10^5, 和1 ≤ a[i] ≤ a.length所以我的代碼是:def firstDuplicate(a):    b = a    if len(list(set(a))) == len(a):        return -1    n = 0    answer = -1    starting_distance = float("inf")    while n!=len(a):        value = a[n]        if a.count(value) > 1:            place_of_first_number = a.index(value)            a[place_of_first_number] = 'string'            place_of_second_number = a.index(value)            if place_of_second_number < starting_distance:                starting_distance = place_of_second_number                answer = value            a=b        n+=1        if n == len(a)-1:            return answer     return answer在該站點進行的 22 個測試中,我全部通過了 #21,因為測試列表很大并且執行時間超過了 4 秒。有什么技巧可以減少執行時間,同時保持代碼大致相同?
查看完整描述

3 回答

?
拉丁的傳說

TA貢獻1789條經驗 獲得超8個贊

您可以遍歷列表,將項目添加到集合中,如果該項目已經在集合中,則它是具有最低索引的重復項,因此您可以簡單地返回該項目; 或者如果您到達循環末尾而沒有找到重復項,則返回 -1:


def firstDuplicate(a):

    seen = set()

    for i in a:

        if i in seen:

            return i

        seen.add(i)

    return -1


查看完整回答
反對 回復 2021-06-22
?
繁花不似錦

TA貢獻1851條經驗 獲得超4個贊

創建一個新集合并在新列表中找到它,如果它返回元素:


def firstDuplicate(a):

    dup = set()

    for i in range(len(a)):

        if a[i] in dup:

            return a[i]

        else:

            dup.add(a[i])

    return -1


查看完整回答
反對 回復 2021-06-22
?
ibeautiful

TA貢獻1993條經驗 獲得超6個贊

這只是一個想法,我沒有驗證它,但它應該可以工作。似乎沒有內存限制,只有時間限制。因此,使用空間來交易時間可能是一種實用的方法。計算復雜度為O(n)。該算法還取決于數字范圍在 1 到 之間的條件len(a)。


def first_duplicate(a):

    len_a = len(a)

    b = [len_a + 1] * len_a

    for i, n in enumerate(a):

        n0 = n - 1

        if b[n0] == len_a + 1:

            b[n0] = len_a

        elif b[n0] == len_a:

            b[n0] = i

    min_i = len_a

    min_n = -1

    for n0, i in enumerate(b):

        if i < min_i:

            min_i = i

            min_n = n0 + 1

    return min_n

更新:


此解決set()方案不如@blhsing的解決方案快。但是,如果它是用 C 實現的,可能就不一樣了——這有點不公平,因為它set()是一個內置函數,它是用 C 實現的,作為 CPython 的其他核心函數。


查看完整回答
反對 回復 2021-06-22
  • 3 回答
  • 0 關注
  • 156 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號