【有书共读】《算法与数据结构题目最优解》(在线编程题总结8)
该书第八章——《数组与矩阵问题》,这部分我列举几个常见的面试题。见我的个人博客:https://blog.csdn.net/zichen_ziqi/article/details/82116525与https://blog.csdn.net/zichen_ziqi/article/details/81417262。主要包括两部分:数组中出现次数超过一半的一般的数字与无序数组中找出何为N的两个数(三个数,四个数)。暂时介绍第一部分,第二部分见详细的链接。
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
1、解法一——时间复杂度为O(N^2)
思路1:简单粗暴,双重循环遍历,找出现次数最多的那个数,再比较出现次数是否超过数组的一半。不详写,谁都能想到。
思路2:时间复杂度为O(N^2)的排序算法 (如冒泡、插入、选择等)+ 求排序后数组的中间数 + 判断中间数出现次数是否超过数组的一半,这部分放在解法二中统一总结。
2、解法二——时间复杂度为O(NlogN),
思路:数组排序后,如果符合条件的数存在,则一定是数组中间那个数。(比如:1,2,2,2,3;或2,2,2,3,4;或2,3,4,4,4等等),这种方法虽然容易理解,但由于涉及到快排sort,其时间复杂度为O(NlogN)并非最优。
def MoreThanHalfNum_Solution(numbers): len1 = len(numbers) if len1==0: return 0 numbers.sort() # 排序 middle = numbers[len1 // 2] #取排序后的中位数 # 判断res是否符合条件,即出现次数大于数组长度的一半 counts = 0 for j in range(len1): if numbers[j] == middle: counts += 1 if counts>len1//2: # python3整除为//,python2为/ return middle else: return 0 if __name__ == '__main__': try: while True: arr = [int(i) for i in input().split()] print(MoreThanHalfNum_Solution(arr)) except: pass
这里可能存在疑问,因为大家都知道非比较排序算法的时间复杂度为O(N),这样最终的时间复杂度也是O(N)!;如果面试的过程中,面试官要求给定的无序数组,不能进行排序又该如何处理?
3、解法三——时间复杂度为O(N)——面试官想要的答案
(1)基于Partition函数的算法,见链接
(2)根据数组特点求解(重点)——剑指offer代码链接
如果有符合条件的数字,则它出现的次数比其他所有数字出现的次数和还要多。
思路:在遍历数组时保存两个值:一是数组中一个数字,一是次数。遍历下一个数字时,若它与之前保存的数字相同,则次数加1,否则次数减1;若次数为0,则保存下一个数字,并将次数置为1。遍历结束后,所保存的数字即为所求。然后再判断它是否符合条件即可。
参考代码为:
(1)基于Partition函数的算法,见链接
(2)根据数组特点求解(重点)——剑指offer代码链接
如果有符合条件的数字,则它出现的次数比其他所有数字出现的次数和还要多。
思路:在遍历数组时保存两个值:一是数组中一个数字,一是次数。遍历下一个数字时,若它与之前保存的数字相同,则次数加1,否则次数减1;若次数为0,则保存下一个数字,并将次数置为1。遍历结束后,所保存的数字即为所求。然后再判断它是否符合条件即可。
参考代码为:
def MoreThanHalfNum_Solution(numbers): len1 = len(numbers) if len1==0: return 0 elif len1>=1: # 遍历每个元素,并记录次数;若与前一个元素相同,则次数加1,否则次数减1 res = numbers[0] # 初始值 count = 1 # 次数 for i in range(1,len1): if count == 0: # 更新result的值为当前元素,并置次数为1 res = numbers[i] count = 1 elif numbers[i] == res: count += 1 # 相同则加1 elif numbers[i] != res: count -= 1 # # 不同则加1 # 判断res是否符合条件,即出现次数大于数组长度的一半 counts = 0 for j in range(len1): if numbers[j] == res: counts += 1 if counts>len1//2: # python3整除为//,python2为/ return res else: return 0 if __name__ == '__main__': try: while True: arr = [int(i) for i in input().split()] print(MoreThanHalfNum_Solution(arr)) except: pass
(3)Python中的cellection包的使用——参考Python collection的使用&代码链接
例子1、若想统计相关元素出现的次数,可以使用Counter:
>from collections import Counter >cnt=Counter() >for w in ['a','b','a','a','a','r','b']: cnt[w]+=1 Counter({'a': 4, 'b': 2, 'r': 1}) # 统计字符串出现的次数 前面有统计sen='hello world',用defaultdict(int) >cnt = Counter() > for ch in 'hello': cnt[ch] = cnt[ch] + 1 Counter({'l': 2, 'o': 1, 'h': 1, 'e': 1})
例子2、:elements()方法按照元素的出现次数返回一个iterator(迭代器),元素以任意的顺序返回,如果元素的计数小于1,将忽略它。
>c = Counter(a=4, b=3, c=1, d=-4,e=0) Counter({'a': 4, 'b': 3, 'c': 1, 'd': -4, 'e':0}) >sorted(c.elements()) ['a', 'a', 'a', 'a', 'b', 'b','b','c'] # most_common(n)返回一个list, list中包含Counter对象中出现最多前n个元素。 >c = Counter('abracadabra') Counter({'a': 5, 'b': 2, 'r': 2, 'd': 1, 'c': 1}) >c.most_common(3) [('a', 5), ('b', 2), ('r', 2)]
因此如果直接利用这个cellection包,上面的代码可写为:
import collections class Solution: def MoreThanHalfNum_Solution(self, numbers): # write code here tmp = collections.Counter(numbers) x = len(numbers)/2 for k, v in tmp.items(): if v > x: return k return 0
(4)用字典的键值对实现,参考:链接
用字典的键值对实现,键存放数组中的数字,值存放数字出现的次数。参考代码如下:
# -*- coding:utf-8 -*- class Solution: def MoreThanHalfNum_Solution(self, numbers): # write code here dict = {} for num in numbers: if num not in dict: dict[num] = 1 else: dict[num]+=1 if dict[num] > len(numbers)/2: return num return 0