在python中計數反轉（對於大整數數組）

我在pyhton中創建一個用於計數反轉的程序，並使用python27進行同樣的操作。我使用分治技術來實現算法（合併排序技巧）。我的程序運行良好的輸入數組的大小爲100（這是我可以驗證的最大值）。現在我測試了我的程序的大小爲50,000和1,00,000的輸入數組，但是我怎麼都無法得到正確的答案。我在下面貼上我的代碼，請指出任何可能的錯誤：在python中計數反轉（對於大整數數組）

f=open('forum.txt') 
    a=[] 
    s=1 
    for line in f: 
     a.append(line) 





def CountInversion(IntegerArray): 
_count=0 
lc=0 
rc=0 
RightArray=[] 
LeftArray=[] 
if len(IntegerArray)>1: 
     LeftArray,lc=CountInversion(IntegerArray[:len(IntegerArray)/2]) 
     RightArray,rc=CountInversion(IntegerArray[len(IntegerArray)/2:]) 
elif len(IntegerArray)==1: 
    return IntegerArray,0 
ResultArray=IntegerArray 
i=0 
l=len(ResultArray) 
j,k=0,0 
for i in range(0,l): 
    if j<len(RightArray) and k<len(LeftArray): 
     if RightArray[j]<LeftArray[k]: 
      ResultArray[i]=RightArray[j] 
      j += 1 
      a=(len(LeftArray)-k) 
      _count = _count + a  
     else: 
      ResultArray[i]=LeftArray[k] 
      k += 1 
elif j<len(RightArray): 
    ResultArray[i]=RightArray[j] 
     j += 1 
elif k<len(LeftArray): 
     ResultArray[i]=LeftArray[k] 
     k += 1   
return ResultArray,(_count+lc+rc) 

arr,b=CountInversion(a) 

print ('end of inversions') 

print b

我也跑在this後由JF塞巴斯蒂安給出的代碼，但結果是一樣的（答案是小輸入正確的，但不能輸入數組大小爲50000或1,00,000）

來源

2013-02-09 nishant mehta

是勉強可讀的解決，但可以有效地通過某種自己一個細小的改動實現合併（這可能是什麼這個代碼試圖數反轉去做）。 – mmgp 2013-02-09 02:13:30

請張貼適當的縮進代碼 - 它確實很重要。 – 2013-02-09 02:16:17

s/1,00,000/100,000 /，SO不會讓我。 – 2013-02-09 02:26:41

您的第一個問題是您的縮進不一致。在幾行你使用製表符而不是空格，這是一個非常糟糕的主意。縮進在Python中很重要，所以如果不注意，很容易出錯。

我認爲你的第二個問題是你比較字符串而不是數字。 Python非常樂意對字符串進行排序，但它會使用字典編輯，當應用於編碼爲字符串的整數時，這可能是意想不到的。例如，字符串"11"將先於字符串"2"排序，因爲它的第一個字符1在ASCII字符集（也是Unicode）中出現在2之前。

正如我在評論中所提到的，目前還不清楚你如何確定你的代碼無法正常工作。可能只是解決上述問題將解決您遇到的問題。如果他們不這樣做，請解釋您如何確定您的結果無效，然後我會嘗試更新此帖並提供進一步的建議。

來源

2013-02-09 03:48:53 Blckknght

非常感謝，它工作！我只是將字符串解析爲int並填充數組。自3天以來一直在掙扎，再次感謝！ – 2013-02-09 08:21:47

問題是通過解析字符串爲int和填充陣列

來源

2013-10-01 19:57:42

通過添加一些示例代碼可以大大提高此答案。 – 2013-10-01 20:21:47

在python中計數反轉（對於大整數數組）

回答

相關問題