Algorithme pour trouver le plus petit entier en échangeant une paire de chiffres dans un entier donné

Comptez D'abord chaque chiffre, stockez-le dans un tableau (counts[10]).

En partant de la gauche, vérifiez les chiffres (voici la description de la boucle):

Vérifiez qu'il y a un chiffre dans counts qui est plus petit que lui. Choisissez le plus petit. Exception: 0 n'est pas autorisé pour le tout premier chiffre.

• S'il y en a un, échangez, vous avez terminé (quittez la boucle!).
• sinon, décrémentez le chiffre dans counts, et passez au chiffre suivant.

Pour chaque chiffre que vous faites O (1) travail. Ainsi, l'ensemble de algo en O(n).

Pour l'échange, vous voulez utiliser les chiffres les moins significatifs (plus à droite). Vous pouvez soit stocker ces emplacements sur la recherche initiale, ou juste avant l'échange, vous pouvez rechercher le premier chiffre correspondant à partir de la fin.

Je voudrais parcourir le tableau en commençant à droite. Stockez le chiffre sur la droite comme le plus petit chiffre et le chiffre maximum et commencez à bouger à gauche, si vous frappez un nouveau plus petit nombre, appelez-le le plus petit potentiel. Si vous continuez à avancer à gauche et que vous trouvez un plus petit nombre, faites du plus petit le potentiel. Si vous trouvez un plus grand nombre, faites un plus petit potentiel le plus petit int et stockez le plus grand en tant que chiffre maximum. Chaque fois que vous frappez un chiffre plus grand que votre plus petit, faites-en le nouveau chiffre maximum. Si vous appuyez sur la fin, swap max digit et le plus petit chiffre. En python (cela fonctionne et est O (n))

def swap_max(digits):
    i = len(digits) - 1
    while i > 0:
        if digits[i] == 0:
            i-= 1
        else:
            break
    max_i = i
    min_i = i
    pot_i = i
    z_i   = -1
    nz_i  = i
    i = len(digits) - 1
    while i >= 0:
        if digits[i] > digits[pot_i]:
            max_i = i
            min_i = pot_i
        if digits[i] < digits[min_i] and digits[i] != 0:
            pot_i = i
        if digits[i] == 0 and z_i == -1:
            z_i = i
        if digits[i] != 0 and i > 0:
            nz_i = i
        i -= 1
    if z_i != -1 and max_i != 0 and max_i < z_i:
        min_i = z_i
        i = nz_i
        max_i = i
    elif max_i == min_i and z_i != -1:
        i = nz_i
        if i < z_i:
            min_i = z_i
            max_i = i

    v = digits[min_i]
    digits[min_i] = digits[max_i]
    digits[max_i] = v
    return digits


#TESTING THE FUNCTION
tests =   [93561,596,10234,120,10091,98761111,1001,1010,1103,120,93218910471211292416]
results = [13569,569,10234,102,10019,18761119,1001,1001,1013,102,13218910471211292496]
tests = map(list,map(str,tests))
results = map(list,map(str,results))
for i in range(len(tests)):
    res ="".join(map(str,swap_max(map(int,tests[i]))))
    print res,"".join(results[i])
    if res=="".join(results[i]):
        print "PASSED\n"
    else:
        print "FAILED\n"

Cela a fini par fonctionner pour tous les exemples. Il a également l'avantage D'être O(1) utilisation de la mémoire.

Voici un algorithme simple O(n):

- Record 'false' for each of ten digit values, 0 through 9
- Work through the number's digits, left-to-right
    - If the digit value is associated with 'true' go to the next digit and continue
    - Record 'true' for this digit
    - Search all the digits to the right for the right-most, smallest digit
      (except zero for the first digit in the number)
      and swap if the lowest digit found (if any) is less than the current digit
    - If swapped, report success and stop
    - If not swapped, go to the next digit and continue
- If we reach the end of the digit list, report a lack of success and stop

Cela peut ne pas sembler être O (n) lors de la première inspection, mais après avoir réalisé que la boucle interne ne peut pas être exécutée plus de dix fois, il devient évident que c'est O(n) depuis O(n - 10 + 10*n) = O(11*n - 10) = O(n).

PseudoCode : O(n)

1) divisez le nombre en chiffres individuels, disons le chiffre [10] (comme indiqué dans une autre réponse). Init incPos = -1.

2) traverser à partir du chiffre le plus à droite, pour trouver le plus à gauche increasingPos (incPos). c'est-à-dire en traversant , comparez K+1 élément avec le kème élément. Pour, chaque chiffre[k] ≠ 0, Si digit[k] >= digit[k+1], puis marque incPos comme k. Traversez jusqu'à gauche le plus et trouvez le le moins incPos.

4) Si incPos = = -1 renvoie num, sinon traversez la forme incPos à n pour trouver le chiffre Right-Most-Minimum (comme décrit dans le bloc ci-dessous), swap avec le chiffre le plus à droite et le retour. (sûrement il y aura au moins 1 chiffre.)

E.g  
93561 ->                IncPos = 0,  Right most minimum : 1 at pos 4 
596   ->                IncPos = 1,  Right most minimum : 6 at pos 2 
10234 ->                IncPos = -1, return 10234  
93218910471211292416 -> IncPos = 0,  Right most minimum : 1 at pos 18 
98761111 ->             IncPos = 0,  Right most minimum : 1 at pos 7 

5) formez le nombre avec de nouveaux chiffres. Numéro de retour.

Légère variation de L'algorithme de Karoly Horvath

Vous pouvez trier le tableau de chiffres dans O(N).

Maintenant, nous avons 2 listes triées et réelle. Réel est notre tableau d'origine.

Itérer sur réel de gauche à droite,

Pour chaque valeur, Pop off éléments de triés jusqu'à ce que nous atteignons une valeur dont la position dans le tableau d'origine est

Si la tête de la valeur de la liste triée est

Le tri a été effectué en temps O (n). Tout au plus nous sautons n éléments du total de la liste triée, et nous itérons sur la liste d'origine une seule fois, de sorte que l'algorithme entier devrait être O(n) dans le temps et l'espace.

Bien sûr, il y a une vérification de cas particulier pour un échange de 0 avec l'élément le plus à gauche, mais cela n'affecte pas la complexité.