如何在O(n)时间内将保持原序的合并数组拆分为两个有序数组？

可以，存在O(n)时间复杂度的拆分方法，具体思路基于贪心策略，步骤如下：

• 初始化两个空数组X和Y，作为最终要得到的两个有序数组
• 遍历数组C中的每一个元素：
  1. 如果X为空，或者当前元素大于等于X的最后一个元素，将其加入X
  2. 否则，将其加入Y（此时必然满足当前元素大于等于Y的最后一个元素，理由见下文）

正确性说明 #

因为C保留了原有序数组A、B各自的元素相对顺序，所以：

• 原数组A的元素在C中是按递增顺序出现的，原数组B的元素同理
• 当某个元素无法加入X时，说明它比X的最后一个元素小，但它在原所属的数组中，必然大于等于之前已经被放入Y的同组元素，因此加入Y后，Y仍保持有序

示例演示 #

以题目中的C: [1, 4, 3, 5, 6, 9, 8, 29, 10, 24, 50, 65]为例：

1. 1 → 加入X → X = [1]
2. 4 ≥ 1 → 加入X → X = [1,4]
3. 3 < 4 → 加入Y → Y = [3]
4. 5 ≥4 → 加入X → X = [1,4,5]
5. 6 ≥5 → 加入X → X = [1,4,5,6]
6. 9 ≥6 → 加入X → X = [1,4,5,6,9]
7. 8 <9 → 加入Y → Y = [3,8]
8. 29 ≥9 → 加入X → X = [1,4,5,6,9,29]
9. 10 <29 → 加入Y → Y = [3,8,10]
   10.24 <29 → 加入Y → Y = [3,8,10,24]
   11.50 ≥29 → 加入X → X = [1,4,5,6,9,29,50]
   12.65 ≥50 → 加入X → X = [1,4,5,6,9,29,50,65]

最终得到的X和Y均为有序数组，整个遍历过程仅需O(n)时间，每个元素仅处理一次，操作均为常数时间。

内容的提问来源于stack exchange，提问作者Hiiiii