python - 在数字列表中找到第二大的

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

最大的问题是你永远不会更接近你的递归基本情况。

基本情况是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，并返回一些可以使算法的其余部分正常工作的内容。

Answer 2

你为什么不这样做：

>>> 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. 使用 pythonsorted函数 -getIlargestVer1
3. 使用堆 -heapIlargest正如@abarnert 建议的那样。

结果：

对于大小从 1 到 ~5000sorted的数组是最好的，对于较大的数组，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 3

@0x90 有正确的想法，但他把它颠倒了。

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

顺便问一下，这是家庭作业吗？如果是这样，您必须使用的算法背后的整个想法是什么？