Распоредите дате бројеве да бисте формирали највећи број


Ниво тешкоће Лако
Често питани у амазонка МакеМиТрип Паитм Зохо
Ред низ

Изјава о проблему

Претпоставимо да имате низ целих бројева. Проблем „Распоредите задате бројеве да би се формирао највећи број“ тражи да се низ распореди на такав начин да излаз треба да буде максимална вредност која се може направити са тим бројевима низа.

Пример

[34, 86, 87, 765]
878676534

Објашњење: Бројеве смо међусобно повезали тако да дају највећу вредност. Имамо највећу вредност 765, али ако је истакнемо, наш излаз ће бити мањи од вредности коју смо добили сада, тако да прво морамо узети 87, а затим 86, а затим се одморити. Резултат треба да почне са цифром одмора.

Алгоритам за слагање задатих бројева да би се формирао највећи број

1 Compare and check which value is lexicographically greater.
2. The greater value will put forward.
3. Return that value.

Објашњење

Од нас је затражено да преуредимо низ на такав начин да унутар бројева низа сви бројеви збирно произведу највећи број који се може формирати бројевима низа. Дакле, овде ћемо улазе узимати као а низ бројева. Ако је дат број, можемо их лако претворити у низове. Питање које се поставља је како пронаћи већи број када се сви бројеви споје. Јер троцифрени број је дефинитивно већи број када га упоредимо са било којим двоцифреним бројем. Али овде морамо да нађемо да би прва цифра броја требала бити већа од било ког броја који је унесен. На овај начин ћемо решити овај проблем.

Користићемо методу упоређивања за манипулацију низовима. Овим ћемо ручно врста наш унос лексикографски. То значи да је почетна цифра већа од било ког другог броја чија је почетна цифра нижа. Тада бисмо је ставили на прво место чија је почетна цифра већа. Затим морамо сортирати све уносе на овај начин, сада то можемо учинити помоћу методе упоређивања која су предефинисане методе језика или можемо прећи сваки низ и пронаћи лексикографски већи низ. Али ефикаснија метода од тога је овде дефинисана.

Сада их морамо само повезати или једноставно одштампати по редоследу којим су сортирани. Такође, требало је да унесемо унос у формату низа, тако да их можемо сортирати редоследом по лексикографском редоследу.

Распоредите дате бројеве да бисте формирали највећи број

код

Ц ++ код за распоређивање задатих бројева у највећи број

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int myCompare(string X, string Y)
{
    string XY = X.append(Y);
    string YX = Y.append(X);

    return XY.compare(YX) > 0 ? 1: 0;
}
void getLargest(vector<string> arr)
{
    sort(arr.begin(), arr.end(), myCompare);

    for (int i=0; i < arr.size() ; i++ )
        cout << arr[i];
}
int main()
{
    vector<string> arr;
    arr.push_back("34");
    arr.push_back("86");
    arr.push_back("87");
    arr.push_back("765");
    getLargest(arr);
    return 0;
}
878676534

Јава код за распоређивање задатих бројева у највећи број

import java.util.Collections;
import java.util.Iterator;
import java.util.Comparator;
import java.util.Vector;

class rearrangNumericString
{
    public static void getLargest(Vector<String> arr)
    {

        Collections.sort(arr, new Comparator<String>()
        {
            @Override
            public int compare(String X, String Y)
            {

                String XY=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 = new Vector<>();
        arr.add("34");
        arr.add("86");
        arr.add("87");
        arr.add("765");
        getLargest(arr);
    }
} 
878676534

Анализа сложености

Сложеност времена

О (Н * | С | запис Н) где "Н" је бројање бројева и | С | означава дужину највећег броја. Сортирање обједињавањем направиће Н логН поређења, али пошто свако поређење траје | С | време у најгорем случају. Сложеност времена такође ће бити Н * | С | логН.

Сложеност простора

О (Н * | С |) где "Н" је бројање бројева. Овде | С | означава дужину нумеричког уноса.