问题描述
设计一个算法，计算出n阶乘中尾部零的个数
样例
11! = 39916800，因此应该返回 2
解析
统计0的个数，就要考虑一下怎么才能产生0，5乘以任何的偶数都会产生0，也就转换成统计5的个数
|
1 2 3 4 5 6 7 |
def zeroCount (n): count = 0 while n > 0: count += n / 5 n = n / 5 return count |
求第k大元素
问题描述
在数组中找到第k大的元素
样例
给出数组 [9,3,2,4,8]，第三大的元素是 4
给出数组 [1,2,3,4,5]，第一大的元素是 5，第二大的元素是 4，第三大的元素是 3，以此类推
解析
利用分治原理，我们来求解
1 、取数组中的任意位置的元素，比如第一个元素作为参考值
2、遍历数组中的元素，比参考值大的放到一组， 小的放到一组，这里我们把等于参考值的也放到大值组。
3、k的值如果比大值组的长度还大就在小值组， 小就在大值组， 如果等于大值组的长度那么参考值就是我们要找的k大元素
4、3步骤得到的数组重复以上步骤（递归操作），直到3步骤得到我们需要的值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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)) |