L'algorithme de manipulation de liste est trop lent

Question

Il existe une suite de n entiers a1, a2, ..., an. Nous devons changer chaque élément de la séquence avec un élément minimal, qui est placé devant lui. S'il n'y a pas un tel élément, nous devons le remplacer par -1. Tous les changements sont simultanés et indépendants.

exemples:

4 3 1 2 1 -> -1 4 3 3 2

5 4 3 2 1 -> -1 5 4 3 2

Mon code est trop lent et ne passe pas les tests avec des erreurs de temporisation lorsque la séquence est trop grande. Comment puis-je améliorer ses performances?

Voici mon code:

public static void main(String[] args) throws InterruptedException { 
    ArrayList<Integer> list = new ArrayList<>(); 
    Scanner scanner = new Scanner(System.in); 
    int nElements = scanner.nextInt(); 
    for (int i = 0; i < nElements; i++) { 
     list.add(scanner.nextInt()); 
    } 
    ArrayList<Integer> newList = new ArrayList<>(); 
    for (int i = 0; i < list.size(); i++) { 
     int tmp = -1; 
     for (int j = i - 1; j >= 0; j--) { 
      if (list.get(i) < list.get(j)) { 
       if (list.get(j) < tmp || tmp == -1) { 
        tmp = list.get(j); 
       } 
      } 
     } 
     newList.add(tmp); 
    } 
    list = newList; 
} 

MISE À JOUR: J'ai oublié de mentionner que la nouvelle valeur doit être supérieure à l'élément que nous changeons.

Answer 1

Grâce au conseil de cpp débutant! L'ensemble d'arbre et la méthode de plafond ont fait le travail:

public static void main(String[] args) throws InterruptedException { 
    ArrayList<Integer> list = new ArrayList<>(); 
    Scanner scanner = new Scanner(System.in); 
    int nElements = scanner.nextInt(); 
    for (int i = 0; i < nElements; i++) { 
     list.add(scanner.nextInt()); 
    } 
    ArrayList<Integer> newList = new ArrayList<>(); 
    TreeSet<Integer> set = new TreeSet<>(); 
    for (Integer aList : list) { 
     Integer tmp = set.ceiling(aList + 1); 
     if (tmp == null) { 
      newList.add(-1); 
     } else { 
      newList.add(tmp); 
     } 
     set.add(aList); 
    } 
    list = newList; 
} 

Merci à tous!

Answer 2

public static void main(String[] args) { 
    int[] values = {10,3,5,7,9,2,2,14,-5,7,9,3}; 

    if (values.length == 0) { return; } 

    int minValue = values[0]; 
    int temp; 
    values[0] = -1; 

    for(int i=1; i<values.length; i++) { 
     temp = values[i]; 
     values[i] = minValue; 
     if (temp < minValue) { 
      minValue = temp; 
     } 
    } 

} 

Vous pouvez simplement vous rappeler la valeur minimale jusqu'à l'élément actuel et le remplacer lorsque vous en avez trouvé un nouveau. Celui-ci s'exécute dans O (N) et ne nécessite pas de mémoire supplémentaire.

Answer 3

Votre approche est actuellement O (n^2) dans le temps, où n est la taille de la liste, en raison de la façon dont les boucles imbriquées sont construites.

Vous n'avez pas besoin de la boucle interne: vous avez déjà une limite supérieure sur la prochaine valeur à ajouter dans la liste, à savoir la valeur précédente dans la nouvelle liste. L'élément suivant ne sera plus petit que si l'élément précédent correspondant dans la liste d'entrée est plus petit. Alors prenez simplement le plus petit de ces deux nombres.

List<Integer> newList = new ArrayList<>(); 
if (list.size() > 0) { newList.add(-1); } 
if (list.size() > 1) { newList.add(list.get(0)); } 
for (int i = 2; i < list.size(); i++) { 
    newList.add(Math.min(list.get(i-1), newList.get(i-1))); 
}