1.前言
昨天碰到一道关于如何解决有序数组的连接问题,这是一个很常见的问题。但是这里要考虑到代码的效率问题,因为要连接的数组都是有序的,这是一个非常重要的前提条件。
2.简单但效率不高的算法
我首先想到的是使用内置的concat方法,然后再对其进行排序,这种方法完全没有考虑到数组是有序的前提条件,代码如下:
3. 取小值插入的方法
大概思路:就是同时对两个数组进行遍历,设置两个标志(i,j)用于记录遍历的位置,将两个数组中较小的那个值插入新数组中,接着再将标志往前移动一个位置,重复比较,直到搜索值都插入到数组中。第一次做的时候判断条件写错了,所以出现了死循环,暴露了自己算法能力还是挺薄弱的。
当时被问到这个问题,第一感觉就是很像”归并算法“,但是又一想使用归并算法是用不上数组有序这个前提条件的。接着又想到了堆排序、快排序等算法,发现就是无法很有效地用上数组有序这个前提条件,最后选择放弃。面试完后依然没有思路,想了好久不知道如何高效的解决这个问题。快回宿舍的时候,师弟说了一句”又要过节了“,”又“字点醒了我,代码如下: