Stratégie de division et de conquête pour fusionner plusieurs tableaux triés

Question

Utilisation de stratégie de division et de conquête Comment fusionner des tableaux triés chacun avec n éléments dans un seul tableau d'éléments k * n?

Comprendre jusqu'à présent: j'ai eu une certaine compréhension sur les étapes à faire diviser pour mieux régner comme:

Diviser la liste des tableaux en deux listes, chacun des tableaux k/2. Fusionner récursivement les tableaux dans les 2 listes et enfin fusionner les 2 tableaux triés résultants dans le tableau de sortie.

Quelques idées et aide nécessaires !!

public int[] merge(int[][] arrays){ 
int k = arrays.length; 
int n = arrays[0].length; 
if size(arrays) == 1: 
return arrays.pop() 
else 
// For longer lengths split the array into two 
    int half = arrays.length/2; 
    int[] first_Half = new int[half]; 
    int[] second_Half = new int[lists.length - half]; 
    return merge(merge(first_half),merge(second_half)); 

---

J'ai essayé passer le tableau 2-Dim liste des listes et a changé ma première et la deuxième moitié en 2 Dim. tableau comme conseillai mais je reçois l'erreur: « méthode kWayMerge(List<List>) dans la fusion de type n'est pas applicable pour les arguments (int[][]) sur la méthode kWayMerge

Voici les modifications apportées et pour la fusion régulière puis-je utiliser Arrays.copyOf ou méthode clone()

?

// solve the problem separately in each sub-array 
      List a = kWayMerge(firstHalf); 

// K-merge operation using divide and conquer strategy 

    public int[] kWayMerge(List<List>array){ // gets a list of lists as input 
      int[][] firstHalf; int[][] secondHalf; 
      if(array.size() == 1) return null; // if currently have 1 array, return it - stop clause 
    else { 
     int half = array.size()/2; 
     firstHalf = new int[half][]; 
     secondHalf = new int[array.size()-half][]; 
     // solve the problem separately in each sub-array 
     List a = kWayMerge(firstHalf); 

    } 
    return merge((firstHalf),(secondHalf)); 
} 

public int[] merge(int[][] arr1, int[][] arr2) { 

    return null; 
} 

Answer 1

diviser pour régner l'approche serait d'avoir une fonction récursive k-way-merge(), qui obtient une liste de listes en entrée, et à chaque étape:

• Si vous curr Entendez 1 tableau, retournez-le (clause d'arrêt)
• Sinon, divisez la liste des listes en deux et appelez pour chaque moitié k-way-merge(). fusionner les deux listes résultantes.

L'aspect principal que vous devez changer dans votre code est en:

int[] first_Half = new int[half]; 
    int[] second_Half = new int[lists.length - half]; 

Ici, vous avez besoin first_half et second_half être int[][], car ils sont en fait la liste des listes.

En outre, dans la dernière ligne:

return merge(merge(first_half),merge(second_half)); 

Notez que la merge() externe est différent, ce n'est pas un appel récursif - mais un appel à « régulier » merge(), qui fusionne deux tableaux en un seul (comme la logique sur la façon de le faire est manquant dans le code, je suppose que vous avez mis en œuvre merge()). A part cela, l'approche semble correcte, mais un peu inefficace, puisque vous copiez l'objet int[][] à chaque itération, plutôt que d'utiliser des index pour "vous souvenir où vous êtes".