进入本章节后，题目开始更多的关注时间和空间两者的转换
题26--数组中数值出现次数超过一半的数
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
本题常规的思路就是对数组首先进行排序，然后再找出超过数组长度一半的数，但这种思路往往比较平淡，本次采用O(n)的思路来解答本题
class solution(object):
def match(self,result,length,numbers):
count=0
for i in range(length):
if numbers[i]==result:
count+=1
if count*2<=length:
return False
return True
def search_number(self,numbers):
length=len(numbers)
if numbers==None or length<=0:
return None
times=1#先初始化计数
result=numbers[0]
for i in range(1,length):
if times==0:
result=numbers[i]
times=1
elif numbers[i]==result:
times+=1
else:
times-=1
if not self.match(result,length,numbers):
return 0
return result
def main():
s=solution()
print (s.search_number([1,2,3,2,2,2,4,5,2]))
if __name__=='__main__':
main()
题27--输出最小的k个数
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
本题也有两种思路，第一种思路就是基于要找的最小k个数，首先以数组中的该位置的值为分界点，把比它小的数放在左边，把比它大的数放在右边，那么最小的k个数即是包含k在内的k个数，时间复杂度为O(nlogk)
另外一种思路适合海量的数据源，它会用到堆（heapq）的相关概念，关于python 中heapq模块的介绍如下：
image.png
常用语法如下：
image.png
关于本题的思路书中是这么说的
image.png
import heapq#输出该模块
class solution(object):
def k_search(self,tinput,k):#两个变量，一个最初的数组，一个需要输出k个最小值
if tinput==None or len(tinput)<k or k<=0:
return None
output=[]#重新建立的一个数组
for i in tinput:
if len(output)<k:
output.append(i)
else:
output=heapq.nlargest(k,output)#利用堆得到k个最大值，这k个最大值由大到小排列
if i>=output[0]:#表明该循环值大于目前堆中的最大值，因此，不用替换，直接进行下次循环
continue
output[0]==i#不然的话就将该值与最大值替换
return output[::-1]#堆逆序，即由小到大排列
def main():
s=solution()
print (s.k_search([4,5,1,6,2.7,3,8],4)
if __name__=='__main__':
main()
