合并排序的数组
难度:
标签:
题目描述
You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.
Initially the number of elements in A and B are m and n respectively.
Example:
Input: A = [1,2,3,0,0,0], m = 3 B = [2,5,6], n = 3 Output: [1,2,2,3,5,6]
Note:
A.length == n + m
代码结果
运行时间: 19 ms, 内存: 16.1 MB
/*
* 思路：
* 1. 使用Java Stream首先合并数组A和B的有效部分。
* 2. 使用Stream进行排序。
* 3. 将排序结果赋值回A中。
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public void merge(int[] A, int m, int[] B, int n) {
int[] merged = IntStream.concat(Arrays.stream(A, 0, m), Arrays.stream(B, 0, n)).sorted().toArray();
System.arraycopy(merged, 0, A, 0, m + n);
}解释
方法:
此题解采用从后向前的归并排序思想。首先检查A数组中是否完全没有初始化元素（m==0），如果是这种情况，则直接将B数组的元素复制到A数组中。如果不是，定义两个指针i和j分别指向A和B中最后一个已初始化的元素。从A的最后开始，比较A[i]和B[j]的大小，将较大的元素放到A的合适位置上，即索引为i+j+1的位置，然后移动相应的指针。如果B中还有剩余的元素（当A的元素都已经被放置好，j仍大于等于0时），将这些元素复制到A数组的前部。
时间复杂度:
O(m + n)
空间复杂度:
O(1)
代码细节讲解
🦆
在这种从后向前的归并排序中，如何确保不会覆盖A中尚未处理的元素？
▷🦆
如果A和B中的元素完全相同，这种算法是否会有特殊的表现或者需要额外的步骤来处理？
▷🦆
为什么在A中没有初始化元素的情况下直接复制B到A，而不是逐个比较？
▷