Java Algo à Trouver le plus petit et le deuxième plus petit nombre dans la liste

Question

Je dois trouver le plus petit et le deuxième plus petit nombre dans une liste.

Puis-je faire cela en utilisant seule boucle? En outre, nous devons considérer le cas de deux occurrences multiples d'un nombre.

Ex: 1. de la liste [20,30,90,50] sortie 20, 30 2. de la liste [30,30,90,50] sortie 30, 30

plz aider

Answer 1

Je suis désolé, en fait, je n'ai pas la liste des entiers. Mais j'ai une liste d'objets.

Quoi qu'il en soit, merci pour l'aide. J'espère que le code suivant fonctionne

if (minimum==0 || obj.getValue() < minimum) { 
    second = minimum; 
    minimum= obj.getValue(); 
} else if (obj.getValue() < second || second==0) { 
    second = obj.getValue(); 
} 

Answer 2

Je veux vous encourager à faire vos devoirs sur votre propre et comprendre les concepts, donc je ne publierons pas de code pour vous, mais voici quelques choses pour vous guider:

• il est possible de faites ceci avec une seule boucle.
• Faire une passe dans la liste, tout le gain de temps le courant plus petit et le deuxième plus petit nombre. Ce sont les plus petits et deuxième plus petit jusqu'à ce point dans la liste.
• A la fin, vous remarquerez (si vous l'avez fait correctement) que vous avez la plus petite et deuxième plus petit nombre.
• Dans le cas d'un numéro en double, assurez-vous d'inclure une vérification égale dans la condition que vous utilisez; à savoir, vous vérifierez des valeurs plus petites, donc utilisez i <= smallest et i <= secondSmallest que vos deux conditions (par opposition à une stricte plus petite que la comparaison).

Answer 3

Appel Collections.min(), puis retirez l'élément que vous avez obtenu de la liste, et l'appeler à nouveau?

List<Integer> list = Arrays.asList(20, 30, 90, 50); 
    List<Integer> copy = new ArrayList<Integer>(list); 
    Integer smallest = Collections.min(copy); // 20 
    copy.remove(smallest); 
    Integer secondSmallest = Collections.min(copy); // 30 

(Faire une copie de ne pas salir avec l'original.)

Ceci est probablement loin d'être la solution la plus performante (De Collections.min() Javadoc: « Cette méthode effectue une itération sur la collection, il faut donc du temps proportionnel à la taille de la collection. "), mais c'est très simple à écrire et à maintenir. :)

Answer 4

Pseudocode seulement puisque c'est devoirs, pour être transformé dans votre langue de choix. En supposant que la liste a deux ou plusieurs numéros dans ce (index 0 et 1):

set lowest to value at index 0. 
set second_lowest to value at index 1. 
if lowest is greater than second_lowest: 
    swap lowest and second_lowest. 
vary idx from 3 to last element: 
    if value at index idx is less than lowest: 
     set second_lowest to lowest 
     set lowest to value at index idx 
    else 
     if value at index idx is less than second_lowest: 
      set second_lowest to value at index idx 

Cela fonctionne en vérifiant essentiellement chaque numéro pour voir si elle devrait être le nouveau plus bas ou nouveau deuxième chiffre le plus bas. Cela peut être fait en une seule fois.

Ce que vous voulez faire est d'exécuter ce programme dans votre tête, en écrivant sur papier ce que les variables sont changées. C'est un bon moyen de comprendre le fonctionnement d'un ordinateur.Considérez la liste [30,20,90,10,50,12,7], suivant les étapes suivantes:

lowest second description 
------ ------ ----------- 
    30  20 store first two elements. 
    20  30 swap them if in wrong order (they are). 
    20  30 90 is not less than either so ignore. 
    10  20 10 is less than lowest (20) so move 
        lowest to second, store 10 to lowest. 
    10  20 50 is not less than either so ignore. 
    10  12 12 is less than second (20) so 
        store 12 to second. 
    7  10 7 is less than lowest (10) so move 
        lowest to second, store 7 to lowest. 

Answer 5

#include <stdio.h> 
#include <limits.h> /* For INT_MAX */ 

/* Function to print first smallest and second smallest elements */ 
void print2Smallest(int arr[], int arr_size) 
{ 
    int i, first, second; 

    /* There should be atleast two elements*/ 
    if(arr_size < 2) 
    { 
    printf(" Invalid Input "); 
    return; 
    }    

    first = second = INT_MAX; 
    for(i = 0; i < arr_size ; i ++) 
    { 

    /*If current element is smaller than first then update both 
     first and second */ 
    if(arr[i] < first) 
    { 
     second = first; 
     first = arr[i]; 
    } 

    /* If arr[i] is in between first and second then update second */ 
    else if (arr[i] < second) 
    { 
     second = arr[i]; 
    } 
    } 
    printf("The smallest element is %d and second Smallest element is %d", 
     first, second); 
} 

/* Driver program to test above function */ 
int main() 
{ 
    int arr[] = {12, 13, 15, 10, 35, 1}; 
    print2Smallest(arr, 6); 
    getchar(); 
    return 0; 
} 

Answer 6

Cela peut être effectué de manière récursive à l'aide BinarySearch. Ci-dessous est un BinarySearch pour trouver le plus petit. Il peut être étendu pour trouver le plus petit et le second plus petit (méthode semblable au tournoi).

public int findSmallest(int[] A, int start, int end){ 
    if(end == start){ 
     return A[start]; 
    }else if(start == end-1){ 
     return Math.min(A[start], A[end]); 
    }else{ 
      int mid = start + (end-start)/2; 
      int min1 = findSmallest(A, start, mid); 
      int min2 = findSmallest(A, mid+1, end); 

      return Math.min(min1, min2);  
    } 
} 

Voici la méthode pour trouver Deuxième plus petit. L'idée de base est de renvoyer le maximum lorsque la taille de la recherche est <=2. Pour le reste de la recherche, retournez min.

public static int findSecondSmallest(int[] A, int start, int end){ 
    if(end == start){ 
     return A[start]; 
    }else if(start == end-1){ 
     return Math.max(A[start], A[end]); 
    }else{ 
      int mid = start + (end-start)/2; 
      int min1 = findSecondSmallest(A, start, mid); 
      int min2 = findSecondSmallest(A, mid+1, end); 

      return Math.min(min1, min2);  
    } 
}