gpt4 book ai didi

c# - 数组拆分 bz 计数

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:18:26 26 4
gpt4 key购买 nike

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

取一个整数 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% 的作用。但我不知道为什么,我已经尝试了所有可能的例子,它对我有用。

最佳答案

我认为您当前的解决方案可行,但它的运行复杂度为 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;
}

关于c# - 数组拆分 bz 计数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37373832/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com