رتب الأعداد المعطاة لتكوين أكبر عدد


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون ميك ماي تريب Paytm زوهو
مجموعة خيط

المشكلة بيان

افترض أن لديك مجموعة من الأعداد الصحيحة. تتطلب مشكلة "ترتيب أرقام معينة لتكوين أكبر رقم" إعادة ترتيب المصفوفة بحيث يكون الناتج هو القيمة القصوى التي يمكن إجراؤها باستخدام هذه الأرقام من المصفوفة.

مثال

[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 سلسلة من الأرقام. إذا تم إعطاء الرقم ، فيمكننا تحويلها بسهولة إلى سلاسل. السؤال الذي يطرح نفسه هو كيفية إيجاد العدد الأكبر عندما تكون جميع الأرقام متسلسلة. لأن الرقم المكون من ثلاثة أرقام هو بالتأكيد رقم أكبر عند مقارنته بأي عدد مكون من رقمين. لكن علينا هنا إيجاد الرقم الأول من الرقم الذي يجب أن يكون أكبر من أي رقم في الإدخال. بهذه الطريقة ، سنحل هذه المشكلة.

سنستخدم طريقة مقارنة للتلاعب بالسلسلة. مع هذا ، سنذهب يدويًا إلى sort مدخلاتنا المعجمية. هذا يعني أنه إذا كان رقم البداية أكبر من أي رقم آخر يكون رقم بدايته أقل. ثم نضعه أولاً الذي يكون رقمه الابتدائي أكبر. ثم يتعين علينا فرز جميع المدخلات بهذه الطريقة ، والآن يمكننا القيام بذلك بمساعدة إما طريقة المقارنة التي هي طرق محددة مسبقًا للغات أو يمكننا اجتياز كل سلسلة ومعرفة السلسلة المعجمية الأكبر. لكن الطريقة الفعالة من ذلك هي الطريقة المحددة هنا.

الآن علينا فقط تجميعها أو طباعتها بالترتيب الذي تم فرزها به. أيضًا ، كان يجب أن نأخذ المدخلات في تنسيق السلسلة ، حتى نتمكن من فرزها بترتيب معجمي.

رتب الأعداد المعطاة لتكوين أكبر عدد

رمز

كود 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 | تسجيل

تعقيد الفضاء

س (N * | S |) أين "N" هو عدد الأعداد. هنا | S | يشير إلى طول المدخلات الرقمية.