如何在給定的時間複雜度python中找到兩個數組中的最小元素

-2

我有2個數組A和B.我試圖從數組A和B中常見的元素中找到最小值。如何在給定的時間複雜度python中找到兩個數組中的最小元素

贊，如果A = [1,3,2,1] & B = [4,2,5,3,2]，所以它應該返回2，因爲它是最小的元素，它來自兩個A & B.我的代碼如下適用於這種情況，但在某些情況下它不起作用。我不知道如何解決它。請幫忙！

def findMin(A, B): 
    A.sort() 
    B.sort() 
    i = 0 
    for x in A: 
     if i < len(B) - 1 and B[i] < x: 
      i += 1 
     if x == B[i]: 
      return x 
    return -1

另外，我想最壞情況下的時間複雜度爲O((N+M)*log(N+M))

來源

2016-08-05 Ashka

什麼情況下不適用？ – Harrison

提出問題並得到完全有效的答案是不公平的，然後用一個額外的約束脩改你的問題，你應該首先說明問題。我已將問題回滾到其原始狀態，因此它不會使現有答案和人們花在這樣做上的時間無效。 –

我投票結束這個問題作爲題外話，因爲這個問題被編輯添加要求，使現有的，很好的答案無效。 –

Itertools鏈的形式給出：

>>> import itertools 
>>> A = [1,3,2,1] 
>>> B = [4,2,5,3,2] 
>>> min(x for x in itertools.chain(A, B) if x in A and x in B) 
2

來源

2016-08-05 20:07:20 Netwave

是否適用於所有人：N和M是範圍[1，..，10000]內的整數，並且數組A和B的每個元素都是[0，..，1000,000,000]範圍內的整數。 – Ashka

使用'在列表中需要按順序掃描列表，所以這裏存在大量的最壞情況... –

a = [1,2,3,4,5,6] 
b = [3,5,7,9] 

shared = (set(a).intersection(b)) 

shared = sorted(shared) 
print shared[0]

返回3

來源

2016-08-05 20:07:34 Harrison

它是否適用於所有：N和M是範圍[1，...，10000]內的整數以及數組A和B是[0，..，1000,000,000]範圍內的整數 – Ashka

這是一個任何機會的作業問題嗎？我不知道你將要使用的數字。只要嘗試一下你的最壞情況的數字，即最高的數字，看看它是否工作。 – Harrison

不是作業問題。只是嘗試一些示例問題。好，謝謝。 – Ashka

我使用set作者提出因爲它會更快實現。您只需要在轉換爲set s的兩個列表的交集處使用min函數。它太簡單，高效並且不需要任何分類。

min(set(A) & set(B))

爲了讓您最初的算法工作，你只需要通過while循環替換第一if：

while i < len(B) - 1 and B[i] < x:

來源

2016-08-05 20:08:30

它是否適用於所有人：N和M是範圍[1，...，10000]內的整數，並且數組A和B中的每個元素都是[0，..，1000,000,000]範圍內的整數 – Ashka

@Ashka是的，它應該工作 –

你扔在那裏排序，你並不真正需要，找到交集使用一組兩個，然後採取分...

>>> A = [1,3,2,1] 
>>> B = [4,2,5,3,2] 
>>> min(set(A).intersection(B)) 
2

這將使你的函數：

def findMin(A, B, default=-1): 
    return min(set(A).intersection(B), default=default)

如果兩個列表之間沒有相交（您似乎已選擇-1），則默認參數爲返回值，但如果您被Python 2.x卡住，則這是一個Python 3.x添加項，你需要通過例外可能處理它，比如：

def findMin(A, B, default=-1): 
    try: 
     return min(set(A).intersection(B)) 
    except ValueError: 
     return default

至於複雜性，其最壞的情況是O(len(A) * len(B))的路口，雖然平均情況是O(min(len(A), len(B))（見time complexity），那麼min操作需要加上頂部是O(N)。

來源

2016-08-05 20:08:30

它是否適用於所有：N和M是範圍[1，..，10000]內的整數，並且數組A和B的每個元素都是範圍[0，..，1000， 000,000] – Ashka

@Ashka是 - 試試:) –

如果有在陣列的大小有很大的區別更快的方法是爲intersection創建set出較小的：

def find(a, b): 
    small, large = sorted([a, b], key=len) 
    return min(set(small).intersection(large), default=-1)

比較100000和10000元素：

import random 
import timeit 

def find_no_sort(a, b): 
    return min(set(a).intersection(b), default=-1) 

a = [random.randrange(0, 100000) for _ in range(100000)] 
random.shuffle(a) 
b = [random.randrange(0, 100000) for _ in range(10000)] 
random.shuffle(b) 

print('Sorted: ', timeit.timeit('find(a, b)', number=100, globals=globals())) 
print('Not sorted: ', timeit.timeit('find_no_sort(a, b)', number=100, globals=globals()))

輸出（Windows 8上的Python 3.5.1）：

Sorted: 0.8935029393830678 
Not sorted: 1.7727491360998975

來源

2016-08-05 20:53:09 niemmi

如何在給定的時間複雜度python中找到兩個數組中的最小元素

回答

相關問題