在數字列表中找到第二大

Question

我必須通過分而治之算法從列表中找到第二大數字和最大數字。問題是，除了使用像a和b這樣的索引的部分，一切都是正確的。因爲它運作得更快。成本更便宜。不需要重寫代碼或發送其他代碼和方法。只要幫助我，請修復它，如果你可以..任何幫助任何想法歡迎。由於

#!/usr/local/bin/python2.7 

def two_max(arr,a,b): 
     n = len(arr) 
     if n==2: 
      if arr[0]<arr[1]: 
      return (arr[1], arr[0]) 
      else: 
      return (arr[0], arr[1]) 

     (greatest_left, sec_greatest_left) = two_max(arr,a (a+b)/2) 
     (greatest_right, sec_greatest_right) = two_max(arr,(a+b)/2,b) 
     if greatest_left < greatest_right: 
      greatest = greatest_right 
      if greatest_left < sec_greatest_left: 
       return (greatest, sec_greatest_left) 
      else: 
       return (greatest, greatest_left) 
     else: 
      greatest = greatest_left 
      if greatest_right < sec_greatest_right: # Line 4 
       return (greatest, sec_greatest_right) 
      else: 
       return (greatest, greatest_right) 

Answer 1

你爲什麼不這樣做的：

>>> def getIlargest(arr, i): 
     if (i <= len(arr) and i > 0): 
      return sorted(arr)[-i] 

>>> a = [1,3,51,4,6,23,53,2,532,5,2,6,7,5,4]  
>>> getIlargest(a, 2) 
53 

---

我把它一步，測試3種方法：

1. 使用計數排序 - getIlargestVer2
2. 使用python sorted函數 - getIlargestVer1
3. 使用堆 - heapIlargest as @abarnert建議。

結果：

在從1尺寸數組〜5000 sorted是最好的，對於較大的陣列的heapq.nlargest用法是贏家：

情節用於之間尺寸陣列[1*150, 55*150]：

在尺寸陣列之間

*全掃描[1 * 150，300 * 150]：*

我使用的代碼在下文中，將3種方法的實現是在setup字符串：

setup = """ 

import heapq, random 

a = random.sample(xrange(1<<30), 150) 
a = a * factor 

class ILargestFunctions: 

    # taken from [wiki][3] and was rewriting it. 
    def counting_sort(self, array, maxval): 
     m = maxval + 1 
     count = {} 
     for a in array: 
      if count.get(a, None) is None: 
       count[a] = 1 
      else: 
       count[a] += 1 
     i = 0 
     for key in count.keys(): 
      for c in range(count[key]): 
       array[i] = key 
       i += 1 
     return array 

    def getIlargestVer1(self, arr, i): 
     if (i <= len(arr) and i > 0): 
       return sorted(arr)[-i] 

    def getIlargestVer2(self, arr, i): 
     if (i <= len(arr) and i > 0): 
       return self.counting_sort(arr, max(arr))[-i] 

    def heapIlargest(self, arr, i): 
     if (i <= len(arr) and i > 0): 
      return heapq.nlargest(i,arr) 

n = ILargestFunctions() 

""" 

爲主線觸發性能計算和繪製收集的數據是：

import timeit 
import numpy as np 
import matplotlib.pyplot as plt 

if __name__ == "__main__": 
    results = {} 
    r1 = []; r2 = []; r3 = []; 
    x = np.arange(1,300,1) 
    for i in xrange(1,300,1): 
     print i 
     factorStr = "factor = " + str(i) + ";" 
     newSetupStr = factorStr + setup 
     r1.append(timeit.timeit('n.getIlargestVer1(a, 100)', number=200, setup=newSetupStr)) 
     r2.append(timeit.timeit('n.getIlargestVer2(a, 100)', number=200, setup=newSetupStr)) 
     r3.append(timeit.timeit('n.heapIlargest(a, 100)', number=200, setup=newSetupStr)) 
     results[i] = (r1,r2,r3) 
    p1 = plt.plot(x, r1, 'r', label = "getIlargestVer1") 
    p2 = plt.plot(x, r2, 'b' , label = "getIlargestVer2") 
    p3 = plt.plot(x, r3, 'g' , label = "heapIlargest") 
    plt.legend(bbox_to_anchor=(1.05, 1), loc=1, borderaxespad=0.) 
    plt.show() 

Answer 2

@的0x90有個一個正確的主意，但他把它扭轉了。

def find_i_largest_element(seq, i): 
    if (i <= len(seq) and i > 0): 
     s = sorted(seq, reverse=True) 
     return s[i-1] 

順便說一句，這是一項家庭作業嗎？如果是這樣，你必須使用的算法背後的想法是什麼？

Answer 3

最大的問題是你永遠不會接近你的遞歸基礎案例。

基本情況是len(arr) == 2。但每次調用自己的時間，你只是通過arr原樣：

(greatest_left, sec_greatest_left) = two_max(arr,a,(a+b)/2) 
    (greatest_right, sec_greatest_right) = two_max(arr,(a+b)/2,b) 

（請注意，我猜在第一個逗號，因爲當你的貼吧，你實際上是呼叫的號碼a的功能，這是不可能做任何有用的事情......）

所以，無論是你的基本情況應當採取a和b進去，就像這樣：

if b-a == 2: 
    if arr[a]<arr[a+1]: 
     return (arr[a+1], arr[a]) 
    else: 
     return (arr[a], arr[a+1]) 

...或者你應該送一片arr，而不是整個事情，在這種情況下，你不需要a和b擺在首位：

(greatest_left, sec_greatest_left) = two_max(arr[:len(a)/2]) 
    (greatest_right, sec_greatest_right) = two_max(arr[len(a)/2:]) 

兩者將解決您的第一個問題。當然，對於大多數輸入來說，功能仍然不是工作。事實上，它只有在列表的長度是2的冪時纔有效。

如果這不是一個足夠好的提示如何解決它：如果b-a是3會發生什麼？顯然你不能將它分成兩半，兩半都是2或更大。因此，您需要爲b-a == 1編寫另一個基本案例，並返回，這將使算法的其餘部分起作用。