京东4.16笔试题解
京东4.16算法岗笔试
第一题：等差数
第二题：找子列的最大中位数
/*******************************/
第一题思路：
称等差数前一位减后一位的差为位差，所有等差数的位差都在[-9,9]，如果确定了一个等差数的位差、任意一位的数字和这个数的长度，就可以确定这个数。
如等差数首位为8，长度为4，位差为-2，则这个数为8642
输入的数字是a，要找大于等于这个数的等差数b
首先可以b的最高位一定是大于或等于s的，且长度等于a（不管a是什么，总可以找到999...9这样的和a等长的等差数）
那么令b最高位等于a最高位，位差从-9到9开始遍历（首位相同时位差越小这个数就越小），直到找到一个合法的等差数就是答案
不合法的情况：1. 某一位的数字小于0或大于9 2.数值小于a
如果找不到合法的等差数，就令b的最高位加1再重复上面的过程
ac，没在本地IDE留下代码就不贴了
/*******************************/
第二题思路：
更新：评论区老哥提醒解法有问题，我再琢磨琢磨
题目要求相邻的两个数字至少一个被选中，也就是说所有奇数位的数字或所有偶数位的数字都被选中（至少被选中，不是说只选中奇数位或只选中偶数位）
可以分成两种情况
首先先将所有奇数位加入到选中的列表中，其余数字加入到未选中列表，重复如下步骤：
1. 计算已选中列表的中位数a
2. 找出未选中列表中最大的数b
3. 如果b > a，则将b移入到已选中列表，否则终止迭代
然后算所有偶数位的情况，将所有偶数位加入到选中的列表，其余步骤同上
两种情况的最大值就是解
上面的做法用排序做会超时，需要优化：
1. 未选中列表用大根堆来存储，优化每次取最大的开销O(n)->O(logn)
2. 已选中列表需要保持有序才能计算中位数，每次插入的时间开销是O(n)，总时间开销相当于插入排序，O(n²)，这步是主要的性能瓶颈，我们用如下的方法优化：
不需要对已选中列表进行排序，我们用一个大根堆和一个小根堆来存储已选中列表，大根堆存前一半元素，小根堆存后一半元素，称为左堆和右堆
总是保持两个堆的大小相等或左比右多一，这样左堆的首元素就是中位数
每次插入新的元素时，将其与左堆和右堆的首元素比较，按大小放入左堆或者右堆，再调整两个堆的大小至相等或左比右多一即可,每次插入时间复杂度为O(logn)
这个思路同力扣295
总时间复杂度为O(nlogn)
代码如下：
import heapq class NumList(): def __init__(self, num_list=None): self.left = [] self.right = [] self.count = 0 heapq.heapify(self.left) heapq.heapify(self.right) if num_list is not None: for num in num_list: self.insert(num) def get_median(self): return -self.left[0] def insert(self, num): self.count += 1 if len(self.left) == 0: heapq.heappush(self.left, -num) elif len(self.right) == 0: heapq.heappush(self.right, num) elif num > self.right[0]: if len(self.right) == len(self.left): temp = heapq.heappop(self.right) heapq.heappush(self.left, -temp) heapq.heappush(self.right, num) else: heapq.heappush(self.right, num) elif num < -self.left[0]: if len(self.right) == len(self.left): heapq.heappush(self.left, -num) else: temp = -heapq.heappop(self.left) heapq.heappush(self.right, temp) heapq.heappush(self.left, -num) else: if len(self.right) == len(self.left): heapq.heappush(self.left, -num) else: heapq.heappush(self.right, num) def max_median(a): n = len(a) # 奇数 chose = NumList() not_chose = [] heapq.heapify(not_chose) for i in range(n): if i%2 == 1: chose.insert(a[i]) else: heapq.heappush(not_chose, -a[i]) while len(not_chose) > 0: med = chose.get_median() max_value = -not_chose[0] heapq.heappop(not_chose) if max_value > med: chose.insert(max_value) else: break ans1 = chose.get_median() # 偶数 chose = NumList() not_chose = [] heapq.heapify(not_chose) for i in range(n): if i%2 == 0: chose.insert(a[i]) else: heapq.heappush(not_chose, -a[i]) while len(not_chose) > 0: med = chose.get_median() max_value = -not_chose[0] heapq.heappop(not_chose) if max_value > med: chose.insert(max_value) else: break ans2 = chose.get_median() print(ans1,ans2)
投递百度等公司10个岗位