问题描述
设计一个算法,计算出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 |
伐木丁丁,鸟鸣嘤嘤
设计一个算法,计算出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大的元素
样例
给出数组 [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)) |