乐趣区

关于算法:合并两个有序数组LeetCode-88

合并两个有序数组,依据题目的条件不同,细节解决也不同。我想先单纯的探讨下合并两个有序数组,不做工夫及空间复杂度的限度。

只合并两个有序数组

这里,只合并两个有序数组,这两个有序数组的长度也只有存储的元素个数那么长。有两种思路,一种是先合并数组,而不论它是否有序,而后将合并之后的数组排序。另一种思路是,在合并数组的过程中,对元素进行排序,合并完结,排序也完结,这种思路借鉴了归并排序的归并过程,即它用到了数组有序这个条件。
一、先将两个数组合并,而后再排序。开拓一个新数组来存储这两个数组中的元素,须要 O(m+n) 的空间复杂度。将两个数组合并,此处不思考这两个数组有序,因而合并数组工夫破费为 O(m+n),而后排序数组(各种排序都可),这里思考想要较好的工夫复杂度,因而用疾速排序,工夫复杂度为 O((m+n)lg(m+n)),综合起来,最终的工夫复杂度为 O((m+n)lg(m+n)),空间复杂度 O(m+n)。
二、开拓一个新的数组 arr,用来存储这两个有序数组中的元素。这里用到归并排序的 merge 办法,行将两个指针指向两个数组头部,而后比拟指针所指的元素,将较小的元素保留到 arr 数组,并将其指针后移。反复下面的步骤,直到两个数组遍历齐全。这种办法,须要循环 m + n 次,因而工夫复杂度为 O(m+n),然而因为须要开拓额定的空间来存储这两个数组的元素,因而空间复杂度为 O(m+n)。

退出移动版