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

回答

相關問題