Trouver les éléments de pic minimum dans un tableau

Question

Question: Étant donné un nombre de tableaux $$a := [2, 7, 8, 5, 1, 6, 3, 9, 4]$$ Vérifiez les conditions ci-dessous, les deux conditions doivent être satisfaites.

\ begin {rassembler} \ text {Si} a [i]> a [i-1] \ text {ou si premier élément} a [i]> a [i + 1] \ end {rassembler}

\ begin {rassembler} \ text {Si} a [i]> a [i + 1] \ text {ou si dernier élément} a [LastIndex]> a [LastIndex - 1] \ end {rassembler}

• 1ère itération - 8, 6, 9 sont des valeurs de crête.

  • Retirez le plus petit élément.
  • Retirer 6.
  • Nouveau arr {2, 7, 8, 5, 1, 3, 9, 4}.
  • Sortie Arr - {6}

• 2ème itération - 8, 9 sont des valeurs de crête.

  • Retirez le plus petit élément.
  • Retirer 8.
  • Nouveau arr {2, 7, 5, 1, 3, 9, 4}.
  • Sortie Arr - {6, 8}

• 3e itération - 7, 9 sont des valeurs de crête.

  • Retirez le plus petit élément.
  • Supprimer 7. Nouveau arr {2, 5, 1, 3, 9, 4}.
  • Sortie Arr - {6, 7, 8}

• 4ème itération - 5, 9 sont des valeurs de crête.

  • Retirez le plus petit élément.
  • Retirer 5.
  • Nouveau arr {2, 1, 3, 9, 4}.
  • Sortie Arr - {6, 7, 8, 5}

• 5ème itération - 2, 9 sont des valeurs de crête.

  • Retirez le plus petit élément.
  • Retirer 2.
  • Nouveau arr {1, 3, 9, 4}.
  • Sortie Arr - {6, 7, 8, 5, 2}

• 6ème itération - 9 sont des valeurs de crête.

  • Retirez le plus petit élément.
  • Supprimer 9.
  • Nouveau arr {1, 3, 4}.
  • Sortie Arr - {6, 7, 8, 5, 2, 9}

• 7ème itération - 4 sont des valeurs de crête.

  • Retirez le plus petit élément.
  • Retirer 4.
  • Nouveau arr {1, 3}.
  • Sortie Arr - {6, 7, 8, 5, 2, 9, 4}

• 8e itération - 3 sont des valeurs de crête.

  • Retirez le plus petit élément.
  • Retirer 3.
  • Nouvel arr {1}.
  • Sortie Arr - {6, 7, 8, 5, 2, 9, 4, 3}

• 9e itération - 1 sont des valeurs de crête.

  • Retirez le plus petit élément.
  • Supprimer 1.
  • Nouvel arr {1}.
  • Sortie Arr - {6, 7, 8, 5, 2, 9, 4, 3, 1}

Production: {6, 8, 7, 5, 2, 9, 4, 3, 1}

Ma solution fonctionne mais je recherche une solution optimisée. S'il vous plaît, faites-moi savoir.

Voici mon code:

public int[] findMinimumPeaks(int[] arr){
        List<Integer> list1 = new ArrayList<Integer>(arr.length);
        int[] output = new int[arr.length];
        for(int i: arr)
            list1.add(i);
        
        for(int i =0; i<arr.length; i++){
            int minIndex = minimumPeakElement(list1);
            output[i] = list1.get(minIndex);
            list1.remove(minIndex);
        }
        return output;
    }
    
    public int minimumPeakElement(List<Integer> list1){
        int minIndex = 0, peakStart = Integer.MAX_VALUE, peakEnd = Integer.MAX_VALUE;
        int peak = Integer.MAX_VALUE, minPeak = Integer.MAX_VALUE;
        
        if(list1.size() >= 2){
            if(list1.get(0) > list1.get(1)) peakStart = list1.get(0);
            if(list1.get(list1.size() - 1) > list1.get(list1.size() - 2)) peakEnd = list1.get(list1.size() - 1);
            if(peakStart < peakEnd){
                minPeak = peakStart;
                minIndex = 0;
            }
            else if(peakEnd < peakStart){
                minPeak = peakEnd;
                minIndex = list1.size() - 1;
            }
        }
        
        for(int i=1; i<list1.size() - 1; i++){
            if(list1.get(i) > list1.get(i + 1) && list1.get(i) > list1.get(i-1)) peak = list1.get(i);
            if(peak < minPeak){
                minPeak = peak;
                minIndex = i;
            } 
        }
        return minIndex;
    }

```

Answer 1

Tu ne feras pas de force brute.

Votre algorithme présente une complexité temporelle quadratique et ne peut pas être récupéré. Vous en avez besoin d'un meilleur.

La première observation à faire est que lorsque vous supprimez le pic, les autres pics restent en place. Cela seul suffit pour voir que la nouvelle analyse de l'ensemble de la matrice est une perte de temps.

Une observation plus importante est qu'une fois que vous supprimez le pic, le nouveau pic peut n'apparaître que dans la position immédiatement adjacente au pic à supprimer. Veuillez prouver ce fait (ou au moins vous convaincre qu'il en est ainsi). Notez également que le pic du nouveau-né serait en général plus petit que les pics existants, le cas échéant.

J'espère que cela suffit pour vous faire avancer.

---

Quant à l'examen approprié:

• Plat est mieux que niché. Il list1.size() >= 2vaut mieux inverser la condition :

    if (list1.size() < 2) {
        // The list consists of a single element, which is a peak,
        // and it resides at index 0
        return 0;
    }
    // Proceed with a general case here
    ....
  

• list1ressemble à un nom étrange. Il n'y a pas d'autres listes, n'est-ce pas?

Answer 2

J'ai quelques suggestions pour votre code.

Ajoutez toujours des accolades à loop&if

À mon avis, c'est une mauvaise pratique d'avoir un bloc de code non entouré d'accolades; J'ai vu tellement de bugs dans ma carrière liés à ça, si vous oubliez d'ajouter les accolades lors de l'ajout de code, vous cassez la logique / sémantique du code.

Extrayez l'expression en variables lorsqu'elle est utilisée plusieurs fois.

Dans votre code, vous pouvez extraire les expressions similaires en variables; cela rendra le code plus court et plus facile à lire. (java.util.List # taille, java.util.List # get, ect)