找到列表中的元素，而無需在Python中排序

Question

我有重複元素1，...，K的列表。例如，對於K = 4：

[4 2 1 1 2 1 1 3 2 ] 

我想查找1，...，K出現在列表中（無需排序）的序列。例如對於上面的序列，結果將是

[4, 2 ,1 ,3 ] 

如何在python中有效地使用較少的運行時編寫此算法。

謝謝！

Answer 1

這裏是另一種方式，即假設在範圍爲1的所有數字，...，K出現（按照問題說明）：

def inOrder(nums): 
    k = max(nums) 
    indices = [nums.index(n) for n in range(1,k+1)] 
    return [n for i,n in sorted(zip(indices,range(1,k+1)))] 

例如

>>> inOrder([4, 2, 1, 1, 2, 1, 1, 3, 2]) 
[4, 2, 1, 3] 

它是O(nk)其中n是第列表的長度。另一方面，它使用的內置方法相當快速，並且如果每個數字的第一次出現平均在列表中稍早，那麼運行時將比最壞的情況好得多。例如，如果你定義：

nums = [random.randint(1,1000) for i in range(10**6)] 

那麼inOrder(nums)評估需要不到一秒鐘（即使列表中有1首萬個條目）。

Answer 2

常規列表，重複數據刪除可能會不夠好：

def f7(seq): 
    seen = set() 
    seen_add = seen.add 
    return [x for x in seq if not (x in seen or seen_add(x))] 

reference

然而，這本質上是O(N)。這是您在一般情況下可以做到的最好的，但您可能從可以做得更好從一個實用的角度來看，一個大類的投入。

def ordered_dedupe_with_constraints(lst, K): 
    output = collections.OrderedDict() 
    len_lst = len(lst) 
    i = 0 
    while len(output) < K and i < len_lst: 
     output.setdefault(lst[i], None) 
     i += 1 
    return list(output) 

這第二個答案使用您在lst最多K不同的元素，以提早結束時k「th元素被添加到輸出的事實。儘管在一般情況下這仍然是O(N)，但您可能會從K << len_lst獲得更好的性能，並且項目已被充分洗牌。當然，您需要通過某種方式提前知道K，而不是重複獲得max（這會破壞我們短路的目的）。

如果這些約束不是這種情況，那麼最好使用參考文獻中報告的功能f7，因爲實施可能比此處的實施更優化。

Answer 3

from collections import OrderedDict 
list_numbers=[4,2,1,1,2,1,1,3,2] 
print list(OrderedDict.fromkeys(list_numbers)) 

這給出了期望的輸出 - [4,2，1,3]

Answer 4

這將是O（k）。

它將通過列表。對於每個元素，如果這是該元素第一次出現，它會將其添加到列表中。

如果有可能列表中的數字大於k或其他非整數元素，請添加額外的檢查以確定它是小於k的整數。此代碼不會確保列表中存在0到k之間的所有數字。

def findSeq(inputList): 
    dict = {} 
    newList = [] 
    for elem in inputList: 
     if elem not in dict: 
      dict[elem] = True # This can be set to anything 
      newList += [elem] 
    return inputList 

我寫這首先是因爲我誤解了你的問題......不想讓它浪費:)。這將檢查列表中的元素是否按順序出現在另一個列表中。

# inList([2, 1, 5], [2, 3, 1, 5]) -> True 
#inList([2, 1, 5], [2, 3, 5, 1]) -> False 

def inList(small, big): 
    i = 0   # index in small 
    j = 0   # index in big 
    while j < len(big): 
     if small(i) == big(j): 
      i += 1 
      j += 1 
      # Any success is guaranteed to happen here, 
      # right after you've found a match 
      if i+1 == len(small): 
       return True 
     else: 
      j += 1 
    return False