一、面试题39：数组中出现次数超过一半的数字

题目描述：

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

详细代码： # -*- coding:utf-8 -*- class Solution: def MoreThanHalfNum_Solution(self, numbers): # write code here if not numbers or len(numbers) <= 0: return 0 length = len(numbers) res = numbers[0] times = 1 for i in range(1, length): if times == 0: res = numbers[i] times = 1 elif res == numbers[i]: times += 1 else: times -= 1 num = 0 for i in numbers: if i == res: num += 1 if num * 2 > length: return res else: return 0

二、面试题40：最小的k个数

题目描述：

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

详细代码： # -*- coding:utf-8 -*- class Solution: def GetLeastNumbers_Solution(self, tinput, k): # write code here import heapq if k > len(tinput) or k <= 0: return [] return heapq.nsmallest(k, tinput)

三、面试题41：数据流中的中位数

题目描述：

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

详细代码： # -*- coding:utf-8 -*- from heapq import * class Solution: def __init__(self): self.minheap = [] self.maxheap = [] def Insert(self, num): if (len(self.minheap) + len(self.maxheap)) & 1: if len(self.minheap) > 0: if num > self.minheap[0]: heappush(self.minheap, num) heappush(self.maxheap, -self.minheap[0]) heappop(self.minheap) else: heappush(self.maxheap, -num) else: heappush(self.maxheap, -num) else: if len(self.maxheap) > 0: if num < -self.maxheap[0]: heappush(self.maxheap,-num) heappush(self.minheap, -self.maxheap[0]) heappop(self.maxheap) else: heappush(self.minheap, num) else: heappush(self.minheap, num) def GetMedian(self, n = None): if (len(self.minheap) + len(self.maxheap)) & 1: return self.minheap[0] else: return (self.minheap[0] - self.maxheap[0]) / 2.0

四、面试题42：连续子数组的最大和

题目描述：

输入一个整形数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O（n）

详细代码： # -*- coding:utf-8 -*- class Solution: def FindGreatestSumOfSubArray(self, array): # write code here if len(array) <= 0: return 0 curSum = 0 greatestSum = float('-inf') for i in range(len(array)): if crSum <= 0: curSum = array[i] else: curSum += array[i] if curSum > greatestSum: greatestSum = curSum return greatestSum

五、面试题43：1~n整数中1出现的次数

题目描述：

输入一个整数n,求1_{n这n个整数的十进制表示中1出现的次数。例如，输入12，1}12这些整数中包含1的数字有1，10，11，12一共出现了5次。

详细代码： # -*- coding:utf-8 -*- class Solution: def NumberOf1Between1AndN_Solution(self, n): # write code here base, sum = 1, 0 while n // base > 0: high, mod = divmod(n, 10 * base) curNum, low = divmod(mod, base) if curNum > 1: sum += high * base + base elif curNum == 1: sum += high * base + low + 1 else: sum += high * base base = 10 * base return sum