Рубрики

Упорядочить данные числа, чтобы сформировать наибольшее число | Комплект 1

Учитывая массив чисел, расположите их так, чтобы получить наибольшее значение. Например, если заданные числа {54, 546, 548, 60}, расположение 6054854654 дает наибольшее значение. И если заданы числа {1, 34, 3, 98, 9, 76, 45, 4}, то расположение 998764543431 дает наибольшее значение.

Простое решение, которое приходит нам в голову, состоит в том, чтобы отсортировать все числа в порядке убывания, но простая сортировка не работает. Например, 548 больше 60, но на выходе 60 предшествует 548. Во втором примере 98 больше 9, но 9 на выходе предшествует 98.

Так, как мы пойдем об этом? Идея состоит в том, чтобы использовать любой алгоритм сортировки, основанный на сравнении .

В используемом алгоритме сортировки вместо использования сравнения по умолчанию напишите функцию сравнения myCompare () и используйте ее для сортировки чисел.

Учитывая два числа X и Y , как myCompare () решит, какое число поставить первым — мы сравниваем два числа XY (Y добавляется в конце X) и YX (X добавляется в конце Y). Если XY больше, то X должен предшествовать Y в выводе, иначе Y должен предшествовать. Например, пусть X и Y равны 542 и 60. Чтобы сравнить X и Y, мы сравниваем 54260 и 60542. Поскольку 60542 больше 54260,
мы ставим Y первым.

Ниже приводится реализация вышеуказанного подхода.

Для простоты кода числа считаются строками, вместо обычного массива используется вектор.

Ниже приведена реализация вышеуказанного подхода:

C ++

// Заданный массив чисел, программа для упорядочения чисел, чтобы сформировать
// наибольшее число
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

  
// Функция сравнения, которая используется sort () в printLargest ()

int myCompare(string X, string Y)

{

    // сначала добавляем Y в конце X

    string XY = X.append(Y);

  

    // затем добавляем X в конце Y

    string YX = Y.append(X);

  

    // Теперь посмотрим, какое из двух сформированных чисел больше

    return XY.compare(YX) > 0 ? 1: 0;

}

  
// Основная функция, которая печатает расположение с наибольшим значением.
// Функция принимает вектор строк

void printLargest(vector<string> arr)

{

    // Сортировка чисел с помощью функции сортировки библиотеки. Функция использует

    // наша функция сравнения myCompare () для сравнения двух строк.

    // Подробнее см. Http://www.cplusplus.com/reference/algorithm/sort/

    sort(arr.begin(), arr.end(), myCompare);

  

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

        cout << arr[i];

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    vector<string> arr;

  

    // вывод должен быть 6054854654

    arr.push_back("54");

    arr.push_back("546");

    arr.push_back("548");

    arr.push_back("60");

    printLargest(arr);

  

   return 0;

}

Джава

// Заданный массив чисел, программа для
// упорядочить числа, чтобы сформировать
// наибольшее число

import java.util.*;

  

class GFG {

  

    // Основная функция, которая печатает

    // расположение с наибольшим значением.

    // Функция принимает вектор строк

    static void printLargest(Vector<String> arr){

      

        Collections.sort(arr, new Comparator<String>(){

  

        // Функция сравнения, которая используется

        // sort () в printLargest ()

        @Override

        public int compare(String X, String Y) {

          

        // сначала добавляем Y в конце X

        String XY=X + Y;

          

        // затем добавляем X в конце Y

        String YX=Y + X;

          

        // Теперь посмотрим, какое из двух сформированных чисел

        // лучше

        return XY.compareTo(YX) > 0 ? -1:1;

    }

    });

          

    Iterator it = arr.iterator();

  

    while(it.hasNext())

        System.out.print(it.next());

      

    }

      

    // драйверная программа

    public static void main (String[] args) {

          

        Vector<String> arr;

        arr = new Vector<>();

          

        // вывод должен быть 6054854654

        arr.add("54");

        arr.add("546");

        arr.add("548");

        arr.add("60");

        printLargest(arr);

    }

}
// Этот код предоставлен Shubham Juneja

python3

# Python3 Программа для получения максимума
# возможное целое число из заданного массива
Количество целых чисел ...

  

  
# пользовательский компаратор для сортировки по
# к аб, ба, как указано в описании

def comparator(a, b):

    ab = str(a) + str(b)

    ba = str(b) + str(a)

    return ((int(ba) > int(ab)) - (int(ba) < int(ab)))

      

def myCompare(mycmp):

      

    # Конвертировать функцию cmp = в функцию key =

    class K(object):

        def __init__(self, obj, *args):

            self.obj = obj

        def __lt__(self, other):

            return mycmp(self.obj, other.obj) < 0

        def __gt__(self, other):

            return mycmp(self.obj, other.obj) > 0

        def __eq__(self, other):

            return mycmp(self.obj, other.obj) == 0

        def __le__(self, other):

            return mycmp(self.obj, other.obj) <= 0

        def __ge__(self, other):

            return mycmp(self.obj, other.obj) >= 0

        def __ne__(self, other):

            return mycmp(self.obj, other.obj) != 0

    return K

# код водителя

if __name__ == "__main__":

    a = [54, 546, 548, 60, ]

    sorted_array = sorted(a, key=myCompare(comparator))

    number = "".join([str(i) for i in sorted_array])

    print(number)

  
# Этот код предоставлен SaurabhTewary

C #

using System.Collections.Generic;

using System;

  

namespace LargestNumberClass

{

    class LargestNumberClass

    {

        // Дан список неотрицательных целых чисел,

        // расположить их так, чтобы они образовывали наибольшее число.

        // Примечание: результат может быть очень большим, поэтому вам нужно

        // вернуть строку вместо целого числа.

  

        public static void LargestNumberMethod(List<int> inputList)

        {

            string output = string.Empty;

  

            List<string> newList = inputList.ConvertAll<string>

            (delegate (int i) { return i.ToString(); });

  

            newList.Sort(MyCompare);

  

            for (int i = 0; i < inputList.Count; i++)

            {

                output = output + newList[i];

            }

  

            if (output[0] == '0' && output.Length > 1)

            {

                Console.Write("0");

            }

            Console.Write(output);

        }

  

        internal static int MyCompare(string X, string Y)

        {

            // сначала добавляем Y в конце X

            string XY = X + Y;

  

            // затем добавляем X в конце Y

            string YX = Y + X;

  

            // Теперь посмотрим, какое из двух сформированных чисел больше

            return XY.CompareTo(YX) > 0 ? -1 : 1;

        }

    }

  

    class Program

    {

        static void Main(string[] args)

        {

            List<int> inputList = new List<int>() { 54, 546, 548, 60 };

            LargestNumberClass.LargestNumberMethod(inputList);

        }

    }

// Этот код предоставлен Дипаком Кумаром Сингхом
}

PHP

<?php
// Дан массив чисел, программа
// упорядочить числа для формирования
// наибольшее число

  
// Функция сравнения, которая используется
// по sort () в printLargest ()

function myCompare($X, $Y

    // сначала добавляем Y в конце X

    $XY = $Y.$X

      

    // затем добавляем X в конце Y

    $YX = $X.$Y

      

    // Теперь посмотрим, какой из двух сформировался

    // число больше

    return strcmp($XY, $YX) > 0 ? 1: 0; 

  
// Основная функция, которая печатает
// расположение с наибольшим значением.
// Функция принимает вектор строк

function printLargest($arr

    // Сортировка номеров с использованием библиотеки сортировки

    // функция. Функция использует наш

    // функция сравнения myCompare () для

    // сравниваем две строки.

    // См. Http://www.cplusplus.com/reference/algorithm/sort/

    // для деталей

    usort($arr, "myCompare"); 

  

    for ($i = 0; $i < count($arr) ; $i++ ) 

        echo $arr[$i]; 

  
// Код драйвера

$arr = array("54", "546", "548", "60"); 

printLargest($arr); 

  
// Этот код предоставлен
// ратбхупендра
?>


Выход:

6054854654

Другой подход: (с помощью itertools ) Используя встроенную библиотеку Python, для выполнения этой задачи можно использовать библиотеку itertools.

# Реализация Python3 это использовать itertools.
# перестановки, закодированные ниже:

  

from itertools import permutations

def largest(l):

    lst = []

    for i in permutations(l, len(l)):

        # предоставляет все перестановки значений списка,

        # сохранить их в списке, чтобы найти максимум

        lst.append("".join(map(str,i))) 

    return max(lst)

  

print(largest([54, 546, 548, 60])) #Output 6054854654

  
# Этот код предоставлен Раманом Монгой

Эта статья составлена Рави Чандрой Энаганти . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Упорядочить данные числа, чтобы сформировать наибольшее число | Комплект 1

0.00 (0%) 0 votes