剑指offer--13

进入本章节后，题目开始更多的关注时间和空间两者的转换
题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()