Leetcode t31: prochain arrangement

Description du sujet

Un tableau entier Disposition Est d'organiser tous ses membres dans un ordre séquentiel ou linéaire.

• Par exemple,arr = [1,2,3] ,Ce qui suit peut être considéré comme arr Disposition：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] .
  Du tableau entier Ordre suivant Est l'ordre plus grand du dictionnaire suivant de ses entiers.Plus officiellement,Si tous les arrangements d'un tableau sont disposés dans un conteneur dans l'ordre de son dictionnaire, du plus petit au plus grand,Donc le tableau Ordre suivant C'est l'arrangement derrière ce conteneur ordonné.S'il n'y a pas d'arrangement plus grand,Alors ce tableau doit être réarrangé dans le plus petit ordre de Dictionnaire（C'est - à - dire:,Ses éléments sont classés par ordre croissant）.

• Par exemple,arr = [1,2,3] L'ordre suivant est [1,3,2] .

• De même,,arr = [2,3,1] L'ordre suivant est [3,1,2] .

• Et arr = [3,2,1] L'ordre suivant est [1,2,3] ,Parce que [3,2,1] Il n'y a pas d'ordre de dictionnaire plus grand.

Pour vous donner un tableau entier nums ,Trouver nums L'arrangement suivant de.Il faut Restez où vous êtes. Modifier,Seuls les espaces constants supplémentaires sont autorisés.

Exemple 1：

Entrée：nums = [1,2,3]
Produits：[1,3,2]

Exemple 2：

Entrée：nums = [3,2,1]
Produits：[1,2,3]

Exemple 3：

Entrée：nums = [1,1,5]
Produits：[1,5,1]

Conseils

1 <= nums.length <= 100
0 <= nums[i] <= 100

Idées

D'abord de droite à gauche. ,Trouver un indice $ind$, Que tous les nombres sur sa droite soient dans l'ordre décroissant .Par exemple :

↓
1432, ind=0

Par la suite,In$[ind+1,nums.length-1]$ Choisissez l'un des plus petits et plus grands livres de $a[ind]$ Nombre de,Avec $a[ind]$ Changer de position,Et va $ind$ Les nombres à droite sont dans l'ordre croissant .

Code

    int findInd(int[] a) {
     // Cherchez de droite à gauche,Trouver un indice, Tous les chiffres à droite vont de grands à petits ,Par exemple:1.432,
        // Alors,Besoin de432（ C'est - à - dire qu'un des plus petits de tous les nombres dans l'ordre inverse ,C'est - à - dire:2）,Remplacer1,Et laisser143Ordre croissant
        int ind = a.length-1;
        while(ind > 0) {
    
            if(a[ind] <= a[ind-1]) ind--;
            else break;
        }
        return ind-1;
	}
	
	void next_permutation(int[] a) {
    
		int ind = findInd(a);
		if(ind == -1) {
    
			Arrays.sort(a);
		}
		else {
    
			int tar = -1;
			for(int i = a.length-1; i > ind; i--) {
    
				if(a[i] > a[ind]) {
    
					tar = i;
					break;
				}
			}
			int t = a[ind]; a[ind] = a[tar]; a[tar] = t;
			Arrays.sort(a, ind+1, a.length);
		}
	}