基于归并排序合并步骤字符串还原原始数组的算法咨询

问题定义 #

给定已排序数组（如[1,2,3,4]）和仅包含'1'、'2'的归并合并选择字符串（如'12212'），其中'1'表示合并阶段取左子数组元素，'2'表示取右子数组元素，需要还原出归并排序前的原始数组（如[2,4,3,1]）。核心难点是处理合并时其中一个子数组取完后，追加剩余元素的环节。

逆向推导解决方案 #

归并排序是拆分后合并的过程，我们通过逆向递归的方式，从已排序数组倒推原始数组，重点解决剩余元素的归属问题：

1. 递归拆分规则 #

对于任意长度为L的数组，归并排序会将其拆分为两个子数组：

• 左子数组长度：left_len = L // 2
• 右子数组长度：right_len = L - left_len

2. 选择字符串的分段逻辑 #

归并排序按后序遍历执行：先处理左子数组的所有合并（对应选择子串的前缀），再处理右子数组的所有合并（对应选择子串的中间段），最后处理当前数组的合并（对应选择子串的后缀）。因此需要先计算左、右子树的选择子串长度，再拆分出当前合并的选择子串：

• 递归计算左子树的选择子串长度left_seq_len
• 递归计算右子树的选择子串长度right_seq_len
• 当前合并的选择子串为总字符串的[left_seq_len : left_seq_len+right_seq_len]之后的部分

3. 处理合并阶段的剩余元素 #

当前合并的选择子串中，每个'1'对应左子数组的一个元素，每个'2'对应右子数组的一个元素。当选择子串长度小于left_len + right_len时，说明存在剩余元素需要追加：

• 统计选择子串中'1'的数量cnt_1，'2'的数量cnt_2
• 左子数组的元素 = 已排序数组中被标记为'1'的元素 + 已排序数组末尾的left_len - cnt_1个元素（若left_len > cnt_1，即左子数组有剩余元素追加）
• 右子数组的元素 = 已排序数组中被标记为'2'的元素 + 已排序数组末尾的right_len - cnt_2个元素（若right_len > cnt_2，即右子数组有剩余元素追加）

4. 递归终止条件 #

当子数组长度为1时，该元素即为原始数组中的元素，直接返回。

示例验证 #

以输入'12212'和已排序数组[1,2,3,4]为例：

1. 顶层数组长度4，拆分为左、右各2个元素。
2. 先递归处理左子数组（排序后为[2,4]），对应选择子串前缀'12'：
   • 左子数组拆分为两个长度1的元素，合并时选择'1'取2，'2'取4，还原出[2,4]。
3. 再递归处理右子数组（排序后为[1,3]），对应选择子串中间段'21'：
   • 右子数组拆分为两个长度1的元素，合并时选择'2'取1，'1'取3，还原出[3,1]。
4. 最后处理顶层合并，对应选择子串后缀'2'：
   • 选择'2'表示先取右子数组的1，然后依次取左子数组的2、右子数组的3、左子数组的4，合并得到[1,2,3,4]，还原出原始数组[2,4,3,1]。

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