1428:面试题 10.01. 合并排序的数组
程序员文章站
2022-07-08 09:47:09
...
问题描述
给定两个排序后的数组 A 和 B,其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法,将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。
示例
输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
思路
我们可以遍历B,对于每个B中的元素都插入到A中合适的位置。这样的时间复杂度是O(m*n). (方法一)
我们可以把数组B接在数组A的后面,然后对整个数组A进行排序。这样的时间复杂度是O((n+m)log(n+m)).(方法二)
我们可以用一个临时的数组,设置两个指针分别指向A和B的开头元素,谁小就把谁复制到新的数组中(即比较出来的是最终的位置)。最后把临时数组的值全部复制到数组A中。这样的时间复杂度是O(n+m), 空间复杂度也是O(n+m)。(方法三)
我们方法三中用临时数组的原因是,我们设置两个指针分别指向A和B的开头元素,没有办法谁小就把谁放在最终的位置,因为这可能会使我们遗失一些值。由于我们选定的某个元素的最终位置上是有元素的,直接覆盖的话我们会丢失这个值(因为指针并未更新,如果强行更新,指针也不知道该指向哪里)。But who care? 我们可以转变思维,设置两个指针指向A和B的开头元素,谁大就把谁放在最终的位置上(这样某个元素的最终位置上是没有元素的(或者可以说有元素,这个元素已经找到了自己的最终位置,可以被覆盖))。这样我们可以省去空间复杂度。 时间复杂度为O(n+m)。(方法四)
图解
为什么方法三要用临时数组?
方法四图解
方法一
Java版
class Solution {
public void merge(int[] A, int m, int[] B, int n) {
for(int b: B){
A[m++] = b;
for(int i = m-1; i > 0; i--){
if(A[i-1]>A[i]){
A[i-1] = A[i-1]^A[i];
A[i] = A[i-1]^A[i];
A[i-1] = A[i-1]^A[i];
}else{
break;
}
}
}
}
}
方法二
Java版
class Solution {
public void merge(int[] A, int m, int[] B, int n) {
for(int b:B){
A[m++] = b;
}
Arrays.sort(A,0,m);
}
}
方法三
Java版
class Solution {
public void merge(int[] A, int m, int[] B, int n) {
int[] tmp = new int[m+n];
int ptrA = 0, ptrB = 0,ptrC = 0;
while(ptrA < m && ptrB < n){
if(A[ptrA]<=B[ptrB]){
tmp[ptrC++] = A[ptrA++];
}else{
tmp[ptrC++] = B[ptrB++];
}
}
while(ptrA<m){
tmp[ptrC++] = A[ptrA++];
}
while(ptrB<n){
tmp[ptrC++] = B[ptrB++];
}
ptrA = 0;
for(int t: tmp){
A[ptrA++] = t;
}
}
}
方法四
Java版
class Solution {
public void merge(int[] A, int m, int[] B, int n) {
int curHead = m+n-1;
while(m > 0 && n > 0){
if(A[m-1]>=B[n-1]){
A[curHead--] = A[--m];
}else{
A[curHead--] = B[--n];
}
}
while(m>0){
A[curHead--] = A[--m];
}
while(n>0){
A[curHead--] = B[--n];
}
}
}
上一篇: python 实现邮件自动发送
下一篇: 用oa系统打开word进行签名出现的问题