सबसे बड़ी संख्या बनाने के लिए दिए गए संख्याओं को व्यवस्थित करें


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना MakeMyTrip Paytm Zoho
ऐरे तार

समस्या का विवरण

मान लीजिए कि आपके पास एक पूर्णांक है। समस्या "सबसे बड़ी संख्या बनाने के लिए दिए गए नंबरों को व्यवस्थित करें" सरणी को इस तरह से पुनर्व्यवस्थित करने के लिए कहता है कि आउटपुट का अधिकतम मूल्य होना चाहिए जो कि एक सरणी के उन नंबरों के साथ बनाया जा सकता है।

उदाहरण

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

व्याख्या

हमें सरणी को इस तरह से पुनर्व्यवस्थित करने के लिए कहा गया है कि सरणी की संख्याओं के भीतर, सभी संख्याएं सामूहिक रूप से सबसे बड़ी संख्या का उत्पादन करेंगी जो कि सरणी की संख्याओं के साथ बनाई जा सकती हैं। इसलिए यहां हम इनपुट के रूप में लेंगे स्ट्रिंग संख्या की। अगर नंबर दिया जाता है तो हम उन्हें आसानी से स्ट्रिंग में बदल सकते हैं। यह सवाल उठता है कि जब सभी संख्याओं को मिलाया जाए तो अधिक से अधिक संख्या कैसे ज्ञात करें। क्योंकि तीन अंकों की संख्या निश्चित रूप से एक बड़ी संख्या है जब हम किसी भी दो अंकों की संख्या के साथ तुलना करते हैं। लेकिन यहां हमें संख्या का पहला अंक ढूंढना होगा जो इनपुट में किसी संख्या से अधिक होना चाहिए। इस तरह, हम इस समस्या को हल करने जा रहे हैं।

हम स्ट्रिंग जोड़तोड़ के लिए एक तुलना विधि का उपयोग करेंगे। इसके साथ, हम मैन्युअल रूप से जा रहे हैं तरह हमारे इनपुट lexicographically। इसका अर्थ यह है कि यदि आरंभिक अंक किसी अन्य संख्या से अधिक है जिसका आरंभिक अंक कम है। फिर हम इसे पहले डालेंगे जिसका शुरुआती अंक अधिक है। फिर हमें इस तरह से सभी इनपुट को सॉर्ट करना होगा, अब हम या तो तुलना विधि की मदद से ऐसा कर सकते हैं जो कि भाषाओं की पूर्वनिर्धारित विधियां हैं या हम प्रत्येक स्ट्रिंग को ट्रैवर्स कर सकते हैं और लेक्सिकोग्राफिक रूप से अधिक स्ट्रिंग का पता लगा सकते हैं। लेकिन उस से कुशल विधि यहाँ परिभाषित विधि है।

अब हमें उन्हें केवल संक्षिप्त करना है या उन्हें उसी क्रम में प्रिंट करना है जिस क्रम में वे क्रमबद्ध हैं। इसके अलावा, हमें इनपुट को स्ट्रिंग प्रारूप में लेना चाहिए, ताकि हम उन्हें लेक्सिकोग्राफिक क्रम में क्रमबद्ध कर सकें।

सबसे बड़ी संख्या बनाने के लिए दिए गए संख्याओं को व्यवस्थित करें

कोड

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

जावा कोड सबसे बड़ी संख्या बनाने के लिए दिए गए नंबरों की व्यवस्था करने के लिए

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 | लॉग एन) जहां "एन" संख्याओं की गिनती है और | एस | सबसे बड़ी संख्या की लंबाई को दर्शाता है। मर्ज सॉर्ट एन logN तुलना कर देगा लेकिन प्रत्येक तुलना लेता है | S | सबसे खराब स्थिति में समय। समय जटिलता भी N * होगी | S | logN।

अंतरिक्ष जटिलता

ओ (एन * | एस |) जहां "एन" संख्याओं की गिनती है। यहाँ | एस | सांख्यिक इनपुट की लंबाई को दर्शाता है।