现有两个已排序的数组 A 和 B,其长度分别为 m 和 n。如果需要将这两个数组合并成一个排序的数组 C,并保证空间复杂度为 O(1),以下哪种方法最适合且可行?
答案解析
A. 将B数组追加到A数组尾部并排序,虽然可行,但需要额外的空间来存储追加的元素,且排序过程的复杂度较高(至少O((m+n)log(m+n)),不符合空间复杂度O(1)的要求。
B. 使用归并排序的思想,需要创建一个新的数组C,其空间复杂度为O(m+n),不满足题目要求的空间复杂度O(1)的要求。
C. 从A和B数组的尾部开始,依次比较元素,并将较大元素放入A数组的尾部。这种原地合并的方式可以达到O(1)的空间复杂度,但前提是A数组的剩余空间足够容纳B数组的所有元素。这里题目没有明确指出A数组空间足够,存在一定的隐形假设。但从提供的排序算法知识点来看,这是最符合题意的解法。
D. 对A和B分别堆排序,本身就至少需要O(1)的空间复杂度,合并后空间复杂度依然是O(1),但是排序后又需要合并,且合并的过程不是原地完成,效率较差,而且合并步骤没有直接利用到已排序的性质。而且这明显是复杂化了问题。
在无额外说明的情况下,本题最合理的解释是假定数组A长度为m+n, 尾部m个为有效数据,尾部n个空间可以存储B数组的数据,所以选用C选项。
正确答案:C