Größte teilbare Teilmenge im Array

Question

Bei einem Array besteht die Aufgabe darin, die größte teilbare Teilmenge im Array zu finden. Eine Teilmenge wird als teilbar bezeichnet, wenn für jedes Paar (x, y) in der Teilmenge entweder x y oder y x teilt.

Beispiel

Input: arr [] = {1, 16, 7, 8, 4} Output: 16 8 4 1 In der Ausgangsteilmenge, für jedes Paar, entweder das erste Element zweite aufteilt oder zweiteilt zuerst.

Input: arr [] = {2, 4, 3, 8} Ausgang: 8 4 2

Hier ist, was ich mit gekommen sind. Die Zeitkomplexität ist O (n^2). Kann es verbessert werden?

public static int[] largestDivisibleSubset2(int[] a){ 

    Arrays.sort(a); 
    int index=0; 
    int maxDivCount=0; 
    for(int i=0;i<a.length;i++){ 
     int currentDivCount=0; 
     for (int j=i;j<a.length;j++) { 
      if(a[j]%a[i]==0){ 
       currentDivCount++; 
      } 
     } 
     if(currentDivCount>maxDivCount){ 
      index = i; 
      maxDivCount = currentDivCount; 
     } 
     currentDivCount = 0; 
    } 
    int[] res = new int[maxDivCount]; 
    int k=0; 
    for(int i=0;i<a.length;i++){ 
     if(a[i]%a[index]==0){ 
      res[k++] = a[i];    
     } 
    } 

    return res; 
} 

Answer 1

Auf modernen Multi-Core-Maschinen (und die deutlich verbesserten Einrichtungen für von ihnen Gebrauch in Java 8) ist es oft einfacher ist, nach Wegen zu suchen alle Kerne, bevor die Optimierung sequenzielle Bearbeitungszeiten zu verwenden. Dies gilt insbesondere dann, wenn die Verringerung der Zeitkomplexität auch die Lesbarkeit oder Wartbarkeit verringert.

Hier ist zum Beispiel eine Lösung für Ihr Problem, die parallele Streams in Java 8 verwendet, während Sie entscheiden, ob Sie einer Untergruppe einen Wert hinzufügen möchten. Auf meiner eigenen alten Maschine kann sie die größte teilbare Teilmenge von 50.000 zufälligen ganzen Zahlen in 14 Sekunden finden (22 Sekunden, wenn ich die parallel Methode entferne). Es gibt klare Optimierungen, aber wenn es keinen bestimmten Grund gibt, wählen Sie zuerst Klarheit. Vor allem in Interviews :-)

public int[] getSubSet(int... set) { 
    int[] largest = new int[0]; 
    for (int value : set) { 
     int[] subset = Arrays.stream(set).parallel() 
       .filter(n -> n % value == 0 || value % n == 0).toArray(); 
     if (subset.length > largest.length) 
      largest = subset; 
    } 
    return largest; 
}