算法 – 公猿一九九零

问题描述

在数组中找到第k大的元素

样例

给出数组 [9,3,2,4,8]，第三大的元素是 4

给出数组 [1,2,3,4,5]，第一大的元素是 5，第二大的元素是 4，第三大的元素是 3，以此类推

解析

利用分治原理，我们来求解

1 、取数组中的任意位置的元素，比如第一个元素作为参考值

2、遍历数组中的元素，比参考值大的放到一组，小的放到一组，这里我们把等于参考值的也放到大值组。

3、k的值如果比大值组的长度还大就在小值组，小就在大值组，如果等于大值组的长度那么参考值就是我们要找的k大元素

4、3步骤得到的数组重复以上步骤（递归操作），直到3步骤得到我们需要的值

def kth(arr, k):
        
        baseV = arr[0]
        lArr = []
        rArr = []
        for v in arr:
            if v >= baseV:
                rArr.append(v)
            else:
                lArr.append(v)
            
        # end condition
        if len(rArr) == k:

            return baseV
        
        elif len(rArr) > k:
        
            # 小值为空时，要加如下条件，否则会进入死循环
            
            if not lArr:
                del rArr[0]
            
            return kth(rArr, k)
        else:
            return kth(lArr, k - len(rArr))

def kth(arr, k):

baseV = arr[0]

lArr = []

rArr = []

for v in arr:

if v >= baseV:

rArr.append(v)

else:

lArr.append(v)

# end condition

if len(rArr) == k:

return baseV

elif len(rArr) > k:

# 小值为空时，要加如下条件，否则会进入死循环

if not lArr:

del rArr[0]

return kth(rArr, k)

else:

return kth(lArr, k - len(rArr))

标签：算法

n的阶乘（n!）结果中尾部0的个数有多少？

问题描述

解析

求第k大元素

问题描述

解析