Ən böyük say Leetcode həlli

Problem bəyanat

The Ən böyük rəqəm LeetCode Həlli - “Ən böyük ədəd” deyir ki, qeyri-mənfi tam ədədlərin siyahısını verərək, biz nömrələri elə yerləşdirməliyik ki, onlar ən böyük ədədi təşkil etsin və onu qaytarsın.

Nəticə çox böyük ola biləcəyi üçün tam ədəd əvəzinə sətir qaytarmalısınız.

Misal:

Input:  nums = [10,2]

Output: "210"

Explanation:

• Bütün mümkün sətirlər [“102″,”210”]-dur.
• İkinci “210” sətirinin ən böyük rəqəmi təşkil etdiyini görə bilərik.

Input:  nums = [3,30,34,5,9]

Output: "9534330"

Explanation:

• 5-i yarada bilərik! = 120 müxtəlif növ nömrələr.
• Onların arasında ən böyük rəqəm “9534330”dur.

Yanaşma

Idea:

1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir Çeşidləmə, ilə lambda funksiyası.
2. Burada əsas fikir iki ədəd n1 və n2 arasında hansının birinci olacağını anlamaqdır?
3. Hesab iki imkan bu iki nömrə üçün:
   1. n1 n2-dən əvvəl gəlir, nəticədə sətir belədir n1 + n2.
   2. n2 n1-dən əvvəl gəlir, nəticədə sətir belədir n2 + n1.
4. Bizə lazımdır müqayisə etmək (n1+n2) və (n2+n1) sətir təsvirini və hansı sətir təmsilinin mümkün olan ən böyük ədədi verəcəyini yoxlayın.
5. Gəlin giriş massivini çeşidləyək və istifadə edəcəyik lambda funksiyası iki ədədi müqayisə etmək. n1 + n2 simli təsvirini n2 + n1 ilə müqayisə edin.
6. Əgər n1 + n2-nin sətir təsviri n2 + n1-dən böyükdürsə, doğru qaytarır, əks halda false qaytarır.
7. Əvvəldən başlayaraq nömrələrin bütün simli təsvirlərini əlavə edin.

Kodu

Ən böyük rəqəm Leetcode C++ Həlli:

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end(),[&](const int& a,const int& b){
            string s1 = to_string(a) + to_string(b);
            string s2 = to_string(b) + to_string(a);
            return s1 > s2;
        });
        string ans = "";
        for(auto& c:nums){
            ans += to_string(c);
        }
        if(ans[0]=='0'){
            return "0";
        }
        return ans;
    }
};

Ən böyük sayı Leetcode Java Həlli:

class Solution {
    public String largestNumber(int[] nums) {
        String[] str = new String[nums.length];
        for(int i=0;i<nums.length;i++){
            str[i] = String.valueOf(nums[i]);
        }
        Arrays.sort( str, (s1, s2) -> (s2+s1).compareTo(s1+s2) );
        if(str[0].charAt(0)=='0'){
            return "0";
        }
        StringBuilder ans = new StringBuilder();
        for(String s:str){
            ans.append(s);
        }
        return ans.toString();
    }
}

Ən böyük say Leetcode həlli üçün mürəkkəblik təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O(KNlogN) burada N giriş massivinin ölçüsü, K isə maksimum uzunluğudur giriş sətri.

Çeşidləmə O(NlogN) vaxtını alır və hər müqayisə O(K) vaxtını alır. Beləliklə, zaman mürəkkəbliyi O(KNlogN)-dir.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1). Burada cavabı saxlamaq üçün istifadə olunan yeri nəzərə almırıq.