算法 – 公猿一九九零

2017年12月18日2017年12月18日

合并两个有序数组

问题

合并两个有序的整数数组A和B变成一个新的有序数组

样例
给出A=[1,2,3,4]，B=[2,4,5,6]，返回 [1,2,2,3,4,4,5,6]

解析

1、从第一个元素拿出两个数组的元素比较，小的放到结果集中并从原数组中剔除，大的不做处理

2、如果其中一个数组元素取尽，那么另一个数组剩下的值全部追加上结果集中

def mergeSortedArr(A, B):
	while True:
		if not B:
			res += A
			break
		if not A:
			res += B
			break
			
		a = A[0]
		b = B[0]
		if a <= b:
			res.append(a)
			del A[0]
		else:
			res.append(b)
			del B[0]
			
	return res

def mergeSortedArr(A, B):

while True:

if not B:

res += A

break

if not A:

res += B

break

a = A[0]

b = B[0]

if a <= b:

res.append(a)

del A[0]

else:

res.append(b)

del B[0]

return res

2017年12月15日2017年12月16日

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

问题描述

设计一个算法，计算出n阶乘中尾部零的个数

样例
11! = 39916800，因此应该返回 2

解析

统计0的个数，就要考虑一下怎么才能产生0，5乘以任何的偶数都会产生0，也就转换成统计5的个数

def zeroCount (n):
	count = 0
	while n > 0:
		count += n / 5
		n = n / 5
		
	return count

def zeroCount (n):

count = 0

while n > 0:

count += n / 5

n = n / 5

return count

2017年12月15日2017年12月16日

求第k大元素

问题描述

在数组中找到第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))