Ең үлкен санды құру үшін берілген сандарды орналастырыңыз


Күрделілік дәрежесі оңай
Жиі кіреді Amazon MakeMyTrip Paytm Зохо
Array 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.

Түсіндіру

Бізден массивті массивтің барлық сандары жиынтықта жиымның сандарымен жасалатын ең үлкен санды шығаратындай етіп өзгертуді сұрады. Сонымен, біз кірістерді а ретінде қабылдаймыз жол сандар. Егер сан берілсе, оларды жолдарға оңай түрлендіре аламыз. Барлық сандарды біріктіргенде үлкен санды қалай табуға болады деген сұрақ туындайды. Үш таңбалы сан кез-келген екі таңбалы санмен салыстырған кезде үлкен сан болатындықтан. Бірақ бұл жерде біз санның бірінші цифры енгізілген сандардың кез-келгенінен үлкен болуы керек екенін табуымыз керек. Осылайша, біз бұл мәселені шешеміз.

Біз жолдарды манипуляциялау үшін салыстыру әдісін қолданамыз. Осымен біз қолмен барамыз сорт біздің лексикографиялық тұрғыдан енгізуіміз. Бұл дегеніміз, егер бастапқы цифр бастапқы цифры төмен болатын кез-келген саннан үлкен болса. Онда біз бірінші орынға кімнің бастапқы цифры үлкен болатындығын қояр едік. Содан кейін біз барлық кірістерді осылай сұрыптауымыз керек, енді біз мұны тілдердің алдын-ала анықталған әдістері болып табылатын салыстыру әдісінің көмегімен жасай аламыз немесе әр жолды айналып өтіп, лексикографиялық жағынан үлкен жолды біле аламыз. Бірақ оған қарағанда тиімді әдіс - мұнда анықталған әдіс.

Енді біз оларды біріктіруіміз керек немесе оларды сұрыпталу реті бойынша жай басып шығаруымыз керек. Сонымен қатар, біз оларды лексикографиялық тәртіп бойынша сұрыптай алатындай етіп, жолды форматта алуымыз керек еді.

Ең үлкен санды құру үшін берілген сандарды орналастырыңыз

код

Ең үлкен санды құру үшін берілген сандарды орналастыруға арналған 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

Күрделілікті талдау

Уақыттың күрделілігі

O (N * | S | журнал N) қайда «N» сандардың саны және | S | ең үлкен санның ұзындығын білдіреді. Біріктіру сұрыптауы N logN салыстыруларын жасайды, бірақ әрбір салыстыру | S | алады ең нашар жағдайда уақыт. Уақыттың күрделілігі N * | S | болады logN.

Ғарыштың күрделілігі

O (N * | S |) қайда «N» сандардың саны. Мұнда | S | сандық енгізу ұзындығын білдіреді.