序列数字替换问题：求数组转为优美格式的最小替换次数

我在完成学习作业时遇到瓶颈，卡在指针搜索方法上，目前只能编写大量if和for语句。现有一个整数数组，示例为int[] numbers = { 0, 0, 1, 1, 1, 0, 0, 1 };，需将其转换为「优美格式」：数组前半部分为连续的0（可零个），后半部分全部为1。例如001111是优美格式，00001011则不是。
允许将每个数字替换为其相反值，需求解转换为优美格式所需的最小替换次数。示例：输入0110，输出1；输入11，输出0。
我目前仅能定位左侧连续0的区间，并将右侧区间的0替换为1，附上当前C#代码，想请教正确的解题方向。

当前代码 #

static void FindZeroSegment(int[] numbers, out int start, out int end)
{
    start = -1;
    end = -1;

    for (int i = 0; i < numbers.Length; i++)
    {
        if (numbers[i] == 0)
        {
            if (start == -1)
            {
                start = i;
            }
            end = i;
        }
        else
        {
            if (start != -1)
            {
                break;
            }
        }
    }
}

static int CountOnesInRightSegment(int[] numbers, int startIndex)
{
    int count = 0;

    for (int i = startIndex + 1; i < numbers.Length; i++)
    {
        if (numbers[i] == 1)
        {
            count++;
        }
        else
            numbers[i] = 1;
    }

    return count;
}
static void Main(string[] args)
{
    int[] numbers = { 0, 0, 0, 1, 0, 0 };
// Output 0, 0, 0, 1, 1, 1

    int start;
    int end;
    FindZeroSegment(numbers, out start, out end);
    
    int rightSegment = CountOnesInRightSegment(numbers, end);

    foreach (var item in numbers)
    {
        Console.Write(item);
    }

}

正确解题方向 #

核心思路 #

要找到最小替换次数，本质是要确定一个分割点：分割点左侧（含分割点）全部变为0，右侧全部变为1；分割点可以在数组最左端（即全1），也可以在最右端（即全0）。我们需要遍历所有可能的分割点，计算每个分割点对应的替换次数，取最小值。

具体步骤 #

1. 预处理统计数组：

   • 计算前缀0的数量数组prefixZero：prefixZero[i]表示从数组开头到第i个元素（含i）中0的个数。
   • 计算后缀1的数量数组suffixOne：suffixOne[i]表示从第i个元素到数组末尾中1的个数。

2. 遍历所有分割点计算替换次数：

   • 全1情况：替换次数为数组中0的总数（所有0都要换成1）。
   • 全0情况：替换次数为数组中1的总数（所有1都要换成0）。
   • 分割点在第k个位置（0<=k<数组长度）：左侧要全为0，替换次数是(k+1) - prefixZero[k]（左侧1的个数）；右侧要全为1，替换次数是(数组长度 - k - 1) - suffixOne[k+1]（右侧0的个数）。总次数为两者之和。
   • 遍历所有情况，记录最小替换次数。

示例实现（C#） #

static int MinReplacementsToBeautiful(int[] numbers)
{
    int n = numbers.Length;
    if (n == 0) return 0;

    // 前缀0计数：prefixZero[i]是[0..i]中0的数量
    int[] prefixZero = new int[n];
    prefixZero[0] = numbers[0] == 0 ? 1 : 0;
    for (int i = 1; i < n; i++)
    {
        prefixZero[i] = prefixZero[i-1] + (numbers[i] == 0 ? 1 : 0);
    }

    // 后缀1计数：suffixOne[i]是[i..n-1]中1的数量
    int[] suffixOne = new int[n];
    suffixOne[n-1] = numbers[n-1] == 1 ? 1 : 0;
    for (int i = n-2; i >= 0; i--)
    {
        suffixOne[i] = suffixOne[i+1] + (numbers[i] == 1 ? 1 : 0);
    }

    int min = int.MaxValue;

    // 情况1：全1
    min = Math.Min(min, n - suffixOne[0]);

    // 情况2：分割点在每个位置k，左侧全0，右侧全1
    for (int k = 0; k < n-1; k++)
    {
        int leftReplace = (k+1) - prefixZero[k];
        int rightReplace = (n - k - 1) - suffixOne[k+1];
        min = Math.Min(min, leftReplace + rightReplace);
    }

    // 情况3：全0
    min = Math.Min(min, n - prefixZero[n-1]);

    return min;
}

static void Main(string[] args)
{
    int[] test1 = {0,1,1,0};
    Console.WriteLine(MinReplacementsToBeautiful(test1)); // 输出1

    int[] test2 = {1,1};
    Console.WriteLine(MinReplacementsToBeautiful(test2)); // 输出0

    int[] test3 = {0,0,1,1,1,0,0,1};
    Console.WriteLine(MinReplacementsToBeautiful(test3)); // 输出2
}

方法优势 #

当前方法只考虑了保留左侧连续0的情况，但最优解可能是混合替换（比如把中间的0保留，左侧的1换成0）。遍历所有分割点的方法能覆盖所有可能的优美格式情况，确保找到最小替换次数。

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