（Binary）總結列表中的元素

我需要對列表中的元素進行求和，包含所有的零或1，以便在列表中有1時結果爲1，否則爲0。（Binary）總結列表中的元素

def binary_search(l, low=0,high=-1): 
    if not l: return -1 
    if(high == -1): high = len(l)-1 
    if low == high: 
     if l[low] == 1: return low 
     else: return -1 
    mid = (low + high)//2 
    upper = [l[mid:high]] 
    lower = [l[0:mid-1]] 
    u = sum(int(x) for x in upper) 
    lo = sum(int(x) for x in lower) 
    if u == 1: return binary_search(upper, mid, high) 
    elif lo == 1: return binary_search(lower, low, mid-1) 
    return -1 

l = [0 for x in range(255)] 
l[123] = 1 
binary_search(l)

我使用的代碼來測試

u = sum(int(x) for x in upper)

在解釋器工作正常，但給我的錯誤

類型錯誤：int（）函數的參數必須是字符串或數字，而不是'列表'

我剛剛開始使用python，並且無法弄清楚發生了什麼問題（我用C++編寫的版本也不起作用）。

有沒有人有任何指針？

另外，我怎麼做的總和，以便它是一個二進制異或，而不是簡單的十進制加法？

來源

2013-07-01 Tom Kealy

定義了哪個'x'？ – arshajii

你只需要['任何'功能]（http://docs.python.org/3/library/functions.html#any）？ –

@BrendanLong是的，事實證明，工作。第一個下午與Python。 –

I need to sum the elements of a list, containing all zeros or ones, so that the result is 1 if there is a 1 in the list, but 0 otherwise.

無需總結整個列表;您可以在第一個位置停止。只需使用any()即可。如果容器內至少有一個真值，則返回True，否則返回True，並且它短路（即，如果在列表的早期發現真值，則不掃描其餘部分）。方便地，1是真的，0不是。

True和算術方面False工作爲1和0（布爾都是整數的一個子類），但如果你想具體爲1和0，只是包裝any()在int()。

來源

2013-07-01 16:05:07 kindall

停止製作嵌套列表。

來源

2013-07-01 16:01:53

謝謝！我今天下午纔開始使用python！ –

I need to sum the elements of a list, containing all zeros or ones, so that the result is 1 if there is a 1 in the list, but 0 otherwise.

這有什麼錯

int(1 in l)

來源

2013-07-01 16:03:10 arshajii

其實你不想要的總和;您想知道upper或lower是否包含1值。只要看看Python的基本容器類型語法的優勢：

if 1 in upper: 
    # etc 
if 1 in lower: 
    # etc

你得到的錯誤，順便究其原因，是因爲你包裹upper和lower一個額外的嵌套列表，當你'試圖拆分l（順便說一句，重命名這個變量）。你只是想它像這樣分割：

upper = the_list[mid:high] 
lower = the_list[:mid-1]

最後，值得注意的是，你的邏輯是很奇怪的。這不是經典意義上的二進制搜索。它看起來像你正在執行「找到該列表中第一次出現1的索引」。即使忽略了已經有內置函數的事實，只需遍歷整個列表，直到找到1即可。現在，你已經有了O(nlogn)時間複雜度（再加上一堆額外的一次性環路），這是非常愚蠢的考慮輸出可以O(n)時間被複制：

def first_one(the_list): 
    for i in range(len(the_list)): 
     if the_list[i] == 1: 
      return i 
    return -1

或課程的更簡單通過使用內置的功能index：

def first_one(the_list): 
    try: 
     return the_list.index(1) 
    except ValueError: 
     return -1

來源

2013-07-01 16:03:34

（Binary）總結列表中的元素

回答

相關問題