配列分割数bs数

Question

私はこの問題を私の教授から得ました。

整数NとXの整数を持つ配列A（空ではない）をとります。配列Aを2つの部分に分割する必要があります。最初の配列Ax（左の配列）には、整数Nと配列Ay（右の配列）に等しい数が含まれています。

はX

数を整数に等しいのインデックス（I）がなければならないAXの0 < = I < X

要素すべきであることを意味してはなりませんAyの中Xおよび要素を整数に等しいです。 A [0..I-1]内のXと等しい要素の数は、A [1 ... 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]配列AのI = 3つの部品として

非対称インデックスi = 4

場合Ax = [3,3,4,9]、Ay = [2,5,3]となる。 Xは整数であり、Nは1

100000に由来することができることは、

を想定Xに等しくするアレイアックス二要素であるがNに等しく、アレイAyのからの2つの要素がありません整数0最悪の場合の時間複雑度はO（N）

なければならない

1. アレイAの要素が整数であり、0から100000までとすることができる

   〜100000であることができます

2. WorstCase空間の複雑さはO（1）でなければならず、入力の記憶は考慮されません。入力配列の

Elementsは

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）の複雑さで実行されると思います。

ここでは、配列内のXの数を最初に数え、次に2つの数のバランスをとる点を探して、最初にcountXを計算することで、O（N）コード内に2つの内部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; 
}