如何使用O（n）时间及O（1）空间成本合并两个排序的整数数组到位 [英] how to merge two sorted integer array in place using O(n) time and O(1) space cost

问题描述

例如，给定一个整数阵列及其两个连续序列的起始位置，那些B1和B2，还设置有位置最后，这表示第二序列的结束位置。从阵列[b1]至阵列[B2-1]和阵列[B2]数组[最后]都是为了分开，如何将其代替合并使用O（n）时间及O（1）空间成本？

For example, given an integer array and its two consecutive sequence 's beginning position which are 'b1' and 'b2', furthermore provided with the position 'last' which indicates the second sequence's ending position. From array[b1] to array [b2-1] and from array [b2] to array[last] are both in order separately, how to merge them in place using O(n) time and O(1) space cost?

推荐答案

这绝不是一个简单的问题; 人还在撰写研究论文的主题（PDF） 。这是可能的，但在实践中很少这样做，因为它是如此复杂得多比标准合并使用暂存空间。

This is by no means a simple problem; people are still writing research papers on the subject (PDF). It is possible, but rarely done in practice because it's so much more complicated than a standard merge using scratch space.

这篇关于如何使用O（n）时间及O（1）空间成本合并两个排序的整数数组到位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！