Array split bz count of

我从我的教授那里得到了这个问题。Array split bz count of

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

装置A的指数（I）应为0 < = I < X

在斧元件必须等于整数Ay的X和元素必须不等于整数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和阵列变种A = [3,3，4,9，2,5，3]

不对称性指数I = 4

至于阵列A的I = 3的零件将是Ax = [3，3，4，9]和Ay = [2，5，3]。其中阵列Ax的两个元件是等于N和从阵列Ay的两个元件不等于X

假定， X是整数，并且可以是从1到100000

N是的整数，并且可以是阵列A的0至100000个

元素是整数，并且可以是从0到100000

最坏情况下的时间复杂度必须是O（N）
最差空间的复杂度必须是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％。但我不知道为什么，我尝试过所有可能的例子，它对我很有用。

来源

2016-05-22 CJHornster

当拆分数组时，元素必须是顺序到起始数组吗？ Ax可以是[3,3,4,2,5,3]而Ay是[]？ – jdweng

该问题不限制您将数组元素混洗。 “Ax中的元素必须等于整数X”，这是否意味着Ax中元素的数量或元素值。 –

@jdweng我不确定这件事，但我可以这样。由于这个部分：A [0..I-1]中等于X的元素数与A [I..N-1]中与X不同的元素数相同（对于K = 0 ，A [0..I-1]不包含任何元素，对于I = N，A [I ..N-1]不包含任何元素。）_ **但我不确定** – CJHornster

我认为你目前的解决方案可以工作，但它运行在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; 
}

来源

2016-05-23 10:21:06

Array split bz count of

回答

相关问题