c# - 数组拆分 bz 计数

Question

我从我的教授那里得到了这个问题。

取一个整数 N 和一个具有 X 个整数的数组 A(非空)。您需要将数组 A 分成两部分，第一个数组 Ax(左数组)包含等于整数 N 的数字，数组 Ay(右数组)包含相同数量的非 N 整数。

表示 A 的索引 (I) 应为 0 < = I < X

Ax 中的元素必须等于整数 X，Ay 中的元素不能等于整数 X

A[0..I-1]中等于X的元素个数与A[I..N-1]中不等于X的元素个数相同。(对于K = 0，A[ 0..I-1]不包含任何元素。对于I = N，A[I ..N-1]不包含任何元素。)

例如 如果 X = 3 且数组 var A = [3, 3, 4, 9, 2, 5, 3]

不对称指数 I = 4

对于 I = 3，数组 A 的部分将是 Ax = [3, 3, 4, 9] 和 Ay = [2, 5, 3]。其中数组Ax的两个元素等于N，数组Ay的两个元素不等于X

假设 X为整数，取值范围为1到100000

N是一个整数，可以是0到100000

数组A的元素是整数，可以是0到100000

1. 最坏情况时间复杂度必须为 O(N)

2. WorstCase 空间复杂度必须为 O(1)，不考虑输入的存储。

可以修改输入数组的元素

    public static int Test1Method(int X, int[] A)
    {
                    int c, j;
        int countLeft, countRight;
        int returnIndex = 0;
        for (int i = 0; i < A.Length; i++)
        {
            countLeft = 0;
            countRight = 0;
            for (j = 0; j <= i; j++)
            {
                if (A[j] == X)
                    countLeft = countLeft + 1;
            }
            for (c = A.Length - 1; c > i; c--)
            {
                if (A[c] != X)
                    countRight = countRight + 1;
            }
            if (countRight == countLeft)
                returnIndex = i + 1;
        }

        int countX = 0;
        for (int i = 0; i < returnIndex; i++)
        {
            if (A[i] == X)
                countX++;
        }

        if (countX == 0)
            return A.Length;

        return returnIndex;
    }

有人告诉我，我的解决方案只能发挥 10% 的作用。但我不知道为什么，我已经尝试了所有可能的例子，它对我有用。

Answer 1

我认为您当前的解决方案可行，但它的运行复杂度为 O(N^2)。

这是一个复杂度为 O(N) 的解决方案，首先计算数组中 X 的个数，然后寻找平衡两个计数的点，一开始计算 countX 有助于我们避免这两个代码中的内部 for 循环。

public static int FindIndexSplit(int X, int[] A)
{
    var countX = A.Count(a => a == X);
    var countXLeft = 0;
    var countNonXRight = A.Length - countX;
    for (var i = 0; i < A.Length; i++)
    {
        if (countXLeft == countNonXRight) return i;
        if (A[i] == X)
        {
            countXLeft += 1;
        }
        else
        {
            countNonXRight -= 1;
        }
    }
    return A.Length;
}