K-komplementäre Paare mit gegebenem Array von ganzen Zahlen effektiv

Question

Ich bin sehr neu in der Programmierung. Ich muss die K-komplementären Paare unter Verwendung eines gegebenen Arrays von ganzen Zahlen effektiv finden. Ich habe den folgenden Code geschrieben. Es beinhaltet die Vervielfältigung. Ich muss diese Duplizierung beseitigen. Bitte helfen Sie mir, diese Duplizierung zu entfernen und schlagen Sie bitte vor, ob es einen effizienteren Weg gibt, dies zu tun.

public class KComplexityOfArray { 


public static StringBuffer oldFunction(int arr[], int k) { 
    int result = 0; 
    StringBuffer sb = new StringBuffer(); 

    for (int i = 0; i < arr.length; i++) { 
     for (int j = 0; j < arr.length; j++) { 
      if (i != j && arr[i] + arr[j] == k) { 
       sb.append(arr[i] + "," + arr[j]); 
       result++; 
      } 
     } 
    } 
    System.out.println(result); 
    return sb; 
} 



public static void main(String[] args) { 
    int[] intArray1 = new int[]{4, 5, 6, 3, 1, 8, -7, -6, 7}; 
    int[] intArray2 = new int[]{1, 2, 7, 5, 6, 3}; 
    int[] intArray = new int[]{4, 5, 6, 3, 1, 8, -7, -6}; 
    int k = 9; 
    System.out.println("No of k complementary pairs : " + oldFunction(intArray2, k)); 
} 

}

Bitte jemand mir helfen, dies zu klären. Dank

Answer 1

Dieser Code falsch ist, wenn man bedenkt zwei verschiedene Elemente bilden ein Paar ersetzen:

for (int i = 0; i < arr.length; i++) { 
    for (int j = 0; j < arr.length; j++) { 

Stattdessen sollten Sie j=i+1:

tun

for (int i = 0; i < arr.length; i++) { 
    for (int j = i+1; j < arr.length; j++) { 

Bitte schlagen Sie vor, wenn es einen besseren effizienten Weg gibt, es zu tun.

Ihre Lösung hat TC O(N^2). Stattdessen können Sie es in O(NlogN) reduzieren. Sehen Sie wie:

1. Sortieren Sie das Array.
2. Verwenden Sie zwei Indexpositionen, i und j, die auf 0 und N-1 bzw. N-1 festgelegt sind.
3. Wenn nun die Summe a[i] und a[j] gleich k ist, drucken Sie es aus. Sonst wenn sum < K, Fortschritt i von 1, sonst j durch 1 reduzieren.
4. Wiederholen Sie Schritt 3 bis (i < j)

Schritt 1 nimmt O(NlogN) und die verbleibenden Schritte unternehmen, um O(N); beide kombiniert O(NLogN)

Answer 2

Wenn ich das richtig das Problem zu verstehen, sollten Sie

for (int j = 0; j < arr.length; j++) { 

mit

for (int j = i+1; j < arr.length; j++) {