通过位翻转有序化比特序列的最少翻转次数快速求解方法

所有符合要求的目标有序序列（所有0在所有1前，包含全0、全1的边界情况），本质都对应一个分割位置：分割点左侧全为0，右侧全为1。分割点可以在序列最开头（对应全1序列），也可以在序列最末尾（对应全0序列），我们只需要计算所有可能分割点对应的翻转次数，取最小值即可。

最高效的计算方式是单次遍历+实时计数，时间复杂度O(n)，空间复杂度O(1)，步骤如下：

• 记输入序列长度为n，先统计序列中1的总数量total_one
• 初始化两个变量：current_one = 0（记录当前遍历位置前，0区范围内1的个数），min_flip = n（初始设为不可能超过的最大值，即全翻一遍的次数）
• 遍历所有可能的分割点k（取值范围从0到n，k表示前k个元素属于0区，剩余元素属于1区）：
  • 计算当前分割点的总翻转次数：0区需要把所有1翻成0，次数为current_one；1区需要把所有0翻成1，次数为(n - k) - (total_one - current_one)，两者相加就是当前总翻转数
  • 如果当前总翻转数小于min_flip，就更新min_flip的值
  • 若k还未到序列末尾，判断当前k位置的元素是否为1，是则给current_one加1，进入下一个分割点的计算

举个实际计算例子：输入序列为10101，长度n=5，总1的数量为3：

• k=0（全1）：总翻转数为总0的数量=2
• k=1（第1位为0区，后4位为1区）：0区有1个1要翻，1区有2个0要翻，总次数3
• k=2（前2位为0区，后3位为1区）：0区有1个1要翻，1区有1个0要翻，总次数2
• k=3（前3位为0区，后2位为1区）：0区有2个1要翻，1区有1个0要翻，总次数3
• k=4（前4位为0区，最后1位为1区）：0区有2个1要翻，1区没有0要翻，总次数2
• k=5（全0）：总翻转数为总1的数量=3
  最终得到最少翻转次数为2。

这个操作确实不属于传统排序范畴：传统排序的核心逻辑是不修改元素本身的值，仅通过交换、移动元素位置实现有序；而该操作完全不调整元素位置，仅通过修改元素取值让序列满足指定的有序规则，更合适的表述如下：

• 针对当前0-1序列的具体场景，最贴切的术语是二值序列最小翻转单调化，特指通过最少的位翻转操作，让二值序列满足非降（0全在1前）要求的操作
• 泛化到通用场景，这类不改变元素位置、仅修改元素取值让序列匹配特定约束模式的操作，一般归类为序列修正或约束对齐赋值，和基于位置交换的排序有本质差异。

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