算法题其实不要慌就行了, 就是太久没做了.
题: 有 3 个数组从小到大, 写一段代码合并成一个数组, 并保证顺序
大致思路:
拆成两个数组合并
构造一个新数组, 为的是不影响原数组, 而且修改数组比插入数字消耗少
因为源数组本身有序, 所以可根据顺序, 减少运算次数
结果数组弄个游标, 初始为 0, 记录操作位置, 从两个数组取出值比较, 小的数加入到结果数组, 再从小的数这个数组再取数比较, 直到大于另外一个数组的数, 时间复杂度为 O(n)
代码:
- # encoding='utf8'
- def list_merge(list_a, list_b):
- '''返回两个数组合并的结果'''
- len_a = len(list_a)
- len_b = len(list_b)
- result = [None for i in range(len_a + len_b)] # 构造返回数组
- cursor_r = -1 # result 游标
- cursor_b = 0 # list_b 游标
- # 依次从数组的最前面取出最小的数, 更新到结果数组
- for item_a in list_a:
- for idx in range(cursor_b, len_b):
- cursor_r += 1 # 移动游标
- item_b = list_b[idx]
- if item_a> item_b:
- result[cursor_r] = item_b
- cursor_b += 1 # 移动 list_b 的游标
- else:
- result[cursor_r] = item_a # 因为 list_a 是 for 循环遍历, 所以不需要游标
- break # 继续从 list_a 取数
- # 因为是采用两两比较, 放入最小的数, 所以会导致丢失最大的数, 这里加入最大数
- last = max(a[-1], b[-1])
- result[-1] = last
- return result
- if __name__ == '__main__':
- a = [1, 2, 3, 4, 5]
- b = [2, 3, 4, 6]
- c = list_merge(a, b)
- print(a,b)
- print(c)
来源: http://www.bubuko.com/infodetail-2995500.html