Comment puis-je manipuler un tableau à faire le plus grand nombre?

Question

Disons que vous avez un tableau d'entiers positifs, de les manipuler, de sorte que la concaténation des entiers de la matrice résultante est le plus grand nombre possible. Ex: {9,1,95,17,5}, résultat: 9955171

Les devoirs de la police: C'était un google phone question d'entrevue et pas de telles ententes ont été signées ;).

Answer 1

Comme d'autres l'ont souligné, un tri lexicographique et la concaténation est proche, mais pas tout à fait correcte. Par exemple, pour le nombre 5, 54, et 56 un tri lexicographique produira {5, 54, 56} (en ordre croissant) ou {56, 54, 5} (par ordre décroissant), mais ce que nous voulons vraiment est {56, 5, 54}, car qui produit le plus grand nombre possible.

Si nous voulons une comparaison de deux nombres qui met en quelque sorte les plus gros chiffres d'abord.

1. Nous pouvons le faire qu'en comparant les chiffres individuels des deux nombres, mais nous devons être prudents lorsque nous parcourons la fin d'un numéro si le numéro d'autres encore a les chiffres restants. Il y a beaucoup de compteurs, de l'arithmétique, et le bord des cas que nous avons pour obtenir le droit.

2. Un mignon solution (également mentionné par @Sarp Centel) permet d'obtenir le même résultat (1), mais avec beaucoup moins de code. L'idée est de comparer la concaténation de deux nombres à l'inverse de la concaténation de ces nombres. Tous les trucs que nous avons à traiter explicitement dans (1) est traitée implicitement.

   Par exemple, pour comparer 56 et 5, nous aimerions le faire régulièrement lexicographique comparaison des 565 de 556. Depuis 565 > 556, nous allons dire que c' 56 est plus "large" qu' 5, et devrait venir en premier. De même, en comparant 54 et 5 signifie que nous allons test 545 < 554, qui nous dit qu' 5 est plus "large" qu' 54.

Voici un exemple simple:

// C++0x: compile with g++ -std=c++0x <filename>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

int main() {
  std::vector<std::string> v = {
    "95", "96", "9", "54", "56", "5", "55", "556", "554", "1", "2", "3"
  };
  std::sort(v.begin(), v.end(),
      [](const std::string &lhs, const std::string &rhs) {
        // reverse the order of comparison to sort in descending order,
        // otherwise we'll get the "big" numbers at the end of the vector
        return rhs+lhs < lhs+rhs;
      });

  for (size_t i = 0; i < v.size(); ++i) {
    std::cout << v[i] << ' ';
  }
}

Lorsqu'il est exécuté, ce code affiche:

9 96 95 56 556 5 55 554 54 3 2 1

Answer 2

En regardant l'exemple {5,54,56}, la façon correcte de l'ordre de ces numéros est lorsque l'on compare les chaînes A et B, nous devrions envisager lexicographique de la commande de A+B avec B+A.

Par exemple:

• Comparer (5,54) devient lexicographique de la comparaison de ("554" avec "545")
• Comparer (5,56) devient lexicographique de la comparaison de ("556" avec "565")
• Comparer (54,56) devient lexicographique de la comparaison de ("5456" avec "5654")

Si nous sorte de cette façon, le tableau qui en résulte est {56,5,54}.

Voici une implémentation Java de cette idée:

public class LexicographicSort implements Comparator<Integer> {

    public int compare(Integer o1, Integer o2) {
        String s1 = o1.toString();
        String s2 = o2.toString();
        return (s2+s1).compareTo(s1+s2);
    }

    public static void main(String[] args) {
        LexicographicSort ls = new LexicographicSort();
        Integer[] nums = {9,1,95,17,5};
        Arrays.sort(nums, ls);
        System.out.println(Arrays.toString(nums));
    }
}

Answer 3

Eh bien , pour vous pouvez essayer ce

• diviser les nombres en caractères individuels
• les trier de manière lexicographique dans l'ordre décroissant
• concat la liste

Vous avez obtenu le plus grand nombre

Answer 4

Ici est la mise en œuvre en c++

#include <stdio.h>
#include <sstream>

using namespace std;

/**
    a = 123
    b = 15
    v1 = 12315
    v2 = 15123
    return (v2 - v1) to make the function sort in descending order
*/
int compare_concatenated_ints(const void *arg1, const void *arg2)
{
    int v1 = *(int*) arg1;
    int v2 = *(int*) arg2;

    stringstream s1, s2;
    s1 << v1 << v2;
    s2 << v2 << v1;

    s1 >> v1;
    s2 >> v2;

    return (v2 - v1);
}

void print_array(int arr[], int count)
{
    for (int i = 0; i < count; ++i){
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main()
{
    int arr[] = {4, 0, 94, 9, 14, 0, 1};    
    int count = sizeof(arr)/sizeof(arr[0]);

    printf("BEFORE\n");
    print_array(arr, count);

    std::qsort(arr, count, sizeof(int), compare_concatenated_ints);

    printf("AFTER\n");
    print_array(arr, count);
}

Answer 5

Je suppose que ça a déjà été résolu. Voici quelques lignes de code en Python à l'aide de la logique déjà discuté dans quelques unes des réponses:

>>li = [9,1,95,17,5]
>>li.sort(cmp=lambda a,b: cmp(int(str(a)+str(b)), int(str(b) + str(a))), reverse=True)

>>output = ""
>>for i in li:
output += str(i)

>>print  output