Array split bz Anzahl der Nummer

Question

Ich habe dieses Problem von meinem prof.

Nimm eine ganze Zahl N und eine Reihe A (nicht leer) mit X ganzen Zahlen. Sie müssen das Array A in zwei Teile aufteilen, von denen das erste Array Ax (linkes Array) die Zahlen enthält, die gleich sind zu Integer N und Array Ay (rechtes Array) enthält die gleiche Anzahl von nicht N ganzen Zahlen.

Bedeutet, dass der Index (I) von A sein sollte 0 < = I < X

Elemente in Ax muss gleich sein X und Elemente in Ay auf ganzzahlige muss nicht gleich sein, um integer X

die Zahl von Elementen gleich X in A [0..I-1] entspricht der Anzahl der Elemente, die sich von X in A [I..N-1] unterscheiden (für K = 0, A [0..I- 1] enthält keine Elemente. für I = N, A [I ..N-1] keine Elemente enthalten.)

beispiel Wenn X = 3 und Array var A = [3, 3, 4, 9, 2, 5, 3]

Asymmetry Index I = 4

Wie bei i = 3 die Teile des Array A wird Ax = [3, 3, 4, 9] und Ay = [2, 5, 3] sein. Bei dem die beiden Elemente der Array Ax sind gleich zu N und zwei Elemente von Array Ay sind nicht gleich zu X

seien angenommen, daß X eine ganze Zahl ist und von 1 bis 100.000

sein kann

N ist eine ganze Zahl und kann 0 bis 100.000

Elemente der Matrix A ganze Zahlen sind und 0 bis 100000

1. Worst-Case Zeitkomplexität sein muss O (N)

2. WorstCase Raumkomplexität muss O (1) sein, Speicherung der Eingabe wird nicht berücksichtigt.

Elemente des Eingangsfeldes kann

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; 
    } 

ich gesagt habe modifiziert werden, dass meine Lösung für 10% nur funktional ist. Aber ich weiß nicht warum, ich habe jedes mögliche Beispiel ausprobiert und es funktioniert für mich.

Answer 1

Ich denke, Ihre aktuelle Lösung funktioniert, aber es läuft in einer O (N^2) -Komplexität.

Hier ist eine Lösung, die in einer O (N) -Komplexität laufen würde, indem zuerst die Anzahl der X im Array gezählt wird und dann nach dem Punkt gesucht wird, der die beiden Zählungen ausgleicht zwei interne for-Schleifen in Ihrem Code.

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; 
}