數組中的重要反轉

我正在研究一個作業問題，以查找整數數組中的重要反轉數。「顯着反轉」的定義如下：數組中的重要反轉

在置換甲顯著反演[一個，一個，一個，...，一個_Ñ]被一個其中a _i> 2 a _j對於一些i < j。因此，例如一個= [4,5,2,1,3]恰好具有3顯著倒位，因爲這種排列一個> 2 ，一個> 2 ，a > 2 a。

該解決方案需要具有O（n log n）複雜性。這需要使用分而治之的方法。我選擇了基於合併排序的解決方案。

我理解的分割操作給出這裏：

def countInversions(list): 
    if(len(list) <= 1): 
     return list, 0 
    else: 
     mid = int(len(list)/2) 
     left, a = countInversions(list[:mid]) 
     right, b = countInversions(list[mid:]) 
     result, c = mergeAndCount(left, right) 
     return result, (a + b + c)

但是我在與合併和計數方法的麻煩。具體計算重要倒數的數量。我通過計算正常的反演次數來調整我的代碼。

def mergeAndCount(left, right): 
    result = [] 
    count = 0 
    i,j = 0,0 
    while(i < len(left) and j < len(right)): 
     if(left[i] > 2*right[j]): 
      count += 1 
     if(left[i] < right[j]): 
      result.append(left[i]) 
      i += 1 
     else: 
      result.append(right[j]) 
      j += 1 

    while(left[i:] or right[j:]): 
     if(left[i:]): 
      if(left[i] > 2*right[j-1]): 
       count += 1 
      result.append(left[i]) 
      i += 1 
     if(right[j:]): 
      if(left[i-1] > 2*right[j]): 
       count += 1 
      result.append(right[j]) 
      j += 1 
    return result, count

所以print(countInversions([4,5,2,1,3]))應該返回3.但是，它返回1

我在尋找我的合併和計數方法的指導。

最終實現：

def countInversions(list): 
    if(len(list) <= 1): 
     return list, 0 
    else: 
     mid = int(len(list)/2) 
     left, a = countInversions(list[:mid]) 
     right, b = countInversions(list[mid:]) 
     result, c = mergeAndCount(left, right) 
     return result, (a + b + c) 

def mergeAndCount(left, right): 
    result = [] 
    count = 0 
    i,j = 0,0 

    while(i < len(left) and j < len(right)): 
     if(left[i] > 2*right[j]): 
      count += len(left)-i 
      j += 1 
     else: 
      i += 1 

    i,j = 0,0 
    while(i < len(left) and j < len(right)): 
     if(left[i] < right[j]): 
      result.append(left[i]) 
      i += 1 
     else: 
      result.append(right[j]) 
      j += 1 

    result.extend(left[i:]) 
    result.extend(right[j:]) 
    return result, count

來源

2014-11-04 piranha

你是幾乎沒有，但有兩個問題：

當你找到left[i] > 2*right[i]你是爲了得出結論，所有的left[i:]中的值大於2*right[i]，因此您應該將您的計數增加len(left(i:])，這與len（左）-i相同。（你只是加1，這就是爲什麼你的值太低。）
你需要將你的合併通道分成兩個階段，一個用於計數重要的反轉，一個用於生成排序的輸出數組。（在正常的反演計數中，這兩個會將i和j移動到相同點，因此可以合併，但對於您的情況則不然。）

固定碼：

def mergeAndCount(left, right): 
    result = [] 
    count = 0 
    i,j = 0,0 

    while(i < len(left) and j < len(right)): 
     if(left[i] > 2*right[j]): 
      count += len(left)-i 
      j += 1 
     else: 
      i += 1 

    i,j = 0,0     
    while(i < len(left) and j < len(right)): 
     if(left[i] < right[j]): 
      result.append(left[i]) 
      i += 1 
     else: 
      result.append(right[j]) 
      j += 1 

    while(left[i:] or right[j:]): 
     if(left[i:]): 
      result.append(left[i]) 
      i += 1 
     if(right[j:]): 
      result.append(right[j]) 
      j += 1 
    return result, count

來源

2014-11-04 22:21:36

數組中的重要反轉

回答

相關問題