Comment pourrais-je trouver les deux plus grands éléments d'une ArrayList en divisant et en vaincre?

Question

J'ai beaucoup de mal à comprendre comment faire ceci de façon récursive et diviser pour régner. Je pensais l'avoir eu il y a un moment, mais ce que j'ai essayé d'utiliser n'a pas fonctionné. J'ai un code qui le fait par O (n) mais ça ne marche pas car ça ne va pas s'appliquer à diviser pour régner. Voici le code O (n):

public void find(ArrayList<Integer> list){ 
    int first = 0; 
    int second = 0; 
    for(int n:list){ 
     if(first < n){ 
      second = first; 
      first = n; 
     } else if(second < n){ 
      second = n; 
     } 
    } 

J'ai essayé de modéliser ce après un tri rapide, mais trouvé que cela ne fonctionnerait pas dans un cas comme [4,3,6] où il suffit de choisir 6 après pivotement sur les trois et immédiatement éliminer le 4, même si c'est le deuxième plus grand élément.

J'ai juste besoin d'aide pour le faire, je n'ai pas besoin de quelqu'un pour poster tout le code. Je veux essayer de comprendre par moi-même, mais j'ai toujours beaucoup de mal à comprendre comment y arriver.

Answer 1

Voici quelque chose que j'écrit sur récursion il y a quelque temps, il devrait être en mesure de vous aider à démarrer:

---

Une méthode récursive fonctionne en brisant un problème plus en plus petits problèmes à chaque fois que la méthode est appelée. Cela vous permet de casser ce qui serait un problème difficile; une somme factorielle, en une série de problèmes plus petits.

Chaque fonction récursive a 2 parties:
1) Le cas de base: La plus basse valeur que nous nous soucions d'évaluer. Habituellement, cela va à zéro ou un.

if (num == 1) 
    return 0; 

2) Le cas général: Le cas général est ce que nous allons appeler jusqu'à ce que nous atteignons le cas de base. Nous appelons la fonction à nouveau, mais cette fois avec 1 moins que la fonction précédente a commencé avec (index de recherche, valeurs, etc). Cela nous permet de travailler notre chemin vers le scénario de base. Cette déclaration signifie que nous allons d'abord appeler la fonction avec 1 moins que ce que cette fonction avec; nous avons commencé avec trois, l'appel suivant commence par deux, l'appel après qui commence par 1 (ce qui déclenche notre scénario de base!)

Une fois que notre scénario de base est atteinte, les méthodes « récursion-out ». Cela signifie qu'ils rebondissent en arrière, dans la fonction qui l'a appelé, en ramenant toutes les données des fonctions en dessous! C'est à ce moment que notre sommation se produit réellement.

Une fois la fonction originale atteinte, nous avons notre sommation finale. Par exemple, supposons que vous vouliez la sommation des 3 premiers entiers, par exemple. Le premier appel récursif est passé le numéro 3.

public static int factorial (int num) { 
    //Base case 
    if (num == 1) { 
     return 1; 
    } 
    //General case 
    return num * factorial(num-1); 

    } 

Marcher dans la fonction appelle:

factorial(3); //Initial function call 

// Devient ..

factorial(1) * factorial(2) * factorial(3) = returned value 

Cela nous donne un résultat de 6!