จัดเรียงตัวเลขที่กำหนดให้เป็นตัวเลขที่ใหญ่ที่สุด


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน 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.

คำอธิบาย

เราถูกขอให้จัดเรียงอาร์เรย์ใหม่ในลักษณะที่ภายในจำนวนของอาร์เรย์ตัวเลขทั้งหมดที่รวมกันจะสร้างจำนวนที่มากที่สุดที่สามารถเกิดขึ้นได้ด้วยตัวเลขของอาร์เรย์ ดังนั้นที่นี่เราจะรับอินพุตเป็นไฟล์ เชือก ของตัวเลข หากได้รับหมายเลขเราสามารถแปลงเป็นสตริงได้อย่างง่ายดาย คำถามที่เกิดขึ้นคือจะหาจำนวนที่มากกว่าได้อย่างไรเมื่อตัวเลขทั้งหมดต่อกัน เนื่องจากตัวเลขสามหลักเป็นจำนวนที่มากกว่าเมื่อเราเปรียบเทียบกับตัวเลขสองหลักใด ๆ แต่ที่นี่เราต้องหาหลักแรกของตัวเลขควรมากกว่าตัวเลขใด ๆ ที่ป้อนเข้า ด้วยวิธีนี้เราจะแก้ปัญหานี้

เราจะใช้วิธีการเปรียบเทียบสำหรับการปรับแต่งสตริง ด้วยสิ่งนี้เราจะไปด้วยตนเอง ประเภท ข้อมูลของเราในเชิงศัพท์ ซึ่งหมายความว่าหากตัวเลขเริ่มต้นมากกว่าตัวเลขอื่น ๆ ที่มีตัวเลขเริ่มต้นต่ำกว่า จากนั้นเราจะใส่ไว้ก่อนซึ่งตัวเลขเริ่มต้นมากกว่า จากนั้นเราต้องเรียงลำดับอินพุตทั้งหมดในลักษณะนี้ตอนนี้เราสามารถทำได้ด้วยความช่วยเหลือของวิธีการเปรียบเทียบซึ่งเป็นวิธีการที่กำหนดไว้ล่วงหน้าของภาษาหรือเราสามารถสำรวจแต่ละสตริงและค้นหาสตริงที่ใหญ่กว่าในเชิงศัพท์ แต่วิธีที่มีประสิทธิภาพมากกว่านั้นคือวิธีการที่กำหนดไว้ที่นี่

ตอนนี้เราต้องเรียงต่อกันหรือพิมพ์ตามลำดับที่เรียงกัน นอกจากนี้เราควรใช้อินพุตในรูปแบบสตริงเพื่อที่เราจะได้เรียงลำดับตามลำดับศัพท์

จัดเรียงตัวเลขที่กำหนดให้เป็นตัวเลขที่ใหญ่ที่สุด

รหัส

รหัส 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 | หมายถึงความยาวของอินพุตตัวเลข