179. Largest Number

 

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

 

179. Наибольшее число

 

Задан массив неотрицательных целых чисел. Расположите их так, чтобы образовалось наибольшее число.

Например, из массива чисел [3, 30, 34, 5, 9] наибольшее можно получить число 9534330.

Примечание: Результат может быть очень большим, поэтому вернуть следует строку, а не целое число.

 

// C++

class Solution {

public:

  string largestNumber(vector<int>& nums) {

       

  }

};

 

// Java

public class Solution {

  public String largestNumber(int[] nums) {

       

  }

}

 

РЕШЕНИЕ

сортировка - компаратор

 

Анализ алгоритма

Преобразуем массив чисел в массив строк. Далее реализуем собственный компаратор.

Если массив чисел содержит множество нулей, как например [0, 0, 0], то ответом должна быть строка “0”, а не “000”.

 

Реализация алгоритма

 

int f(string a, string b)

{

  return a + b > b + a;

}

 

class Solution

{

public:

  string largestNumber(vector<int> &num)

  {

    vector<string> s;

    char temp[1000];

 

Преобразуем массив чисел в массив строк s.

 

    for(int i = 0; i < num.size(); i++)

    {

      sprintf(temp,"%d",num[i]);

      s.push_back((string)temp);

    }

 

Отсортируем массив строк согласно компаратору f.

 

    sort(s.begin(),s.end(),f);

 

Произведем конкатинацию строк массива s в одну строку.

 

    string res;

    for(int i = 0; i < s.size(); i++)

      res = res +  s[i];

 

Удалим ведущие нули.

 

    while ((res[0] == '0') && (res.size() > 1))

      res.erase(res.begin());

    return res;

  }

};

 

Java реализация

 

public class Solution

{

  public String largestNumber(int[] nums)

  {

    String[] arr = new String[nums.length];

    for(int i = 0; i < nums.length; i++)

      arr[i] = String.valueOf(nums[i]);

 

    Arrays.sort(arr, new Comparator<String>()

    {

      public int compare(String a, String b)

      {

        return (b+a).compareTo(a+b);

      }

    });

    String res = "";

    for(int i = 0; i < arr.length; i++)

      res += arr[i];    

/*    

    for(String temp : arr)

      res += temp;

*/     

    if (res.charAt(0) == '0') res = "0";

    return res;

  }

}

 

Java реализация – отдельный компаратор

 

class Solution

{

  public static class MyFun implements Comparator<String>

  {

    public int compare(String a, String b)

    {

      return (b+a).compareTo(a+b);

    }

  }

 

  public String largestNumber(int[] nums)

  {

    String[] arr = new String[nums.length];

    for(int i = 0; i < nums.length; i++)

      arr[i] = String.valueOf(nums[i]);

 

    Arrays.sort(arr, new MyFun());

    String res = "";

    for(int i = 0; i < arr.length; i++)

      res += arr[i];    

 

    if (res.charAt(0) == '0') res = "0";

    return res;

  }

}