Տրված թվերը դասավորեք ամենամեծ թիվը կազմելու համար


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon MakeMyTrip- ը Paytm Zoho
Դասավորություն String

Խնդիրի հայտարարություն

Ենթադրենք, որ դուք ունեք ամբողջ թվերի զանգված: «Տրված թվերը դասավորել ամենամեծ թիվը կազմելու համար» խնդիրը պահանջում է զանգվածը վերադասավորել այնպես, որ ելքը լինի առավելագույն արժեքը, որը կարելի է կատարել զանգվածի այդ թվերի հետ:

Օրինակ

[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.

բացատրություն

Մեզ խնդրել են զանգվածը վերադասավորել այնպես, որ զանգվածի համարների մեջ բոլոր թվերը հավաքականորեն առաջ տանեն ամենամեծ թիվը, որը կարող է կազմվել զանգվածի թվերի հետ: Այսպիսով, այստեղ մենք մուտքերը վերցնելու ենք որպես a լարային թվերի Եթե ​​համարը տրված է, մենք կարող ենք դրանք հեշտությամբ վերածել տողերի: Հարց է առաջանում, թե ինչպես գտնել ավելի մեծ թիվ, երբ բոլոր թվերը միավորված են: Քանի որ երեք նիշանոց թիվը հաստատ ավելի մեծ թիվ է, երբ այն համեմատում ենք ցանկացած երկնիշ թվի հետ: Բայց այստեղ մենք պետք է գտնենք, որ համարի առաջին նիշը պետք է ավելի մեծ լինի, քան մուտքագրված թվերից որևէ մեկը: Այս կերպ մենք պատրաստվում ենք լուծել այս խնդիրը:

Լարերի մանիպուլյացիաների համար մենք կօգտագործենք համեմատության մեթոդ: Դրանով մենք ձեռքով գնում ենք տեսակ մեր մուտքագրումը բառարանագրորեն: Սա նշանակում է, որ եթե մեկնարկային թվանշանն ավելի մեծ է, քան ցանկացած այլ թիվ, որի սկզբնական նիշն ավելի ցածր է: Հետո առաջինը կդնեինք, որի սկզբնական նիշն ավելի մեծ է: Դրանից հետո մենք պետք է տեսակավորենք բոլոր մուտքերը այս եղանակով, հիմա մենք դա կարող ենք անել կամ համեմատության մեթոդի օգնությամբ, որը լեզուների կանխորոշված ​​մեթոդներ է, կամ կարող ենք անցնել յուրաքանչյուր տողից և պարզել բառարանագրորեն ավելի մեծ տողը: Բայց դրանից արդյունավետ մեթոդը այստեղ սահմանված մեթոդն է:

Այժմ մենք պետք է պարզապես դրանք միացնենք կամ պարզապես տպենք այնպես, ինչպես ըստ դասավորվածության: Բացի այդ, մենք պետք է մուտքագրեինք լարային ձևաչափով, որպեսզի կարողանանք դրանք տեսակավորել ըստ բառարանագրական կարգի:

Տրված թվերը դասավորեք ամենամեծ թիվը կազմելու համար

Կոդ

C ++ կոդ ՝ տրված համարները դասավորելու համար ՝ ամենամեծ թիվը կազմելու համար

#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

Java կոդ ՝ տրված համարները դասավորելու համար ՝ ամենամեծ թիվը կազմելու համար

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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (N * | S | տեղեկամատյան N) որտեղ «Ն» թվերի հաշվարկն է և | Ս | նշանակում է ամենամեծ թվի երկարությունը: Միաձուլման տեսակավորումը կդարձնի N logN համեմատություն, բայց քանի որ յուրաքանչյուր համեմատություն տանում է | S | ժամանակը վատագույն դեպքում: Timeամանակի բարդությունը կլինի նաև N * | S | մուտք

Տիեզերական բարդություն

O (N * | S |) որտեղ «Ն» թվերի հաշվարկն է: Այստեղ | Ս | նշանակում է թվային մուտքի երկարությունը: