లెక్సికోగ్రాఫికల్ నంబర్లు లీట్‌కోడ్ సొల్యూషన్


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది ByteDance
లోతు మొదటి శోధన

సమస్యల నివేదిక

”లెక్సికోగ్రాఫికల్ నంబర్స్” సమస్యలో మనకు ఒక సంఖ్య ఇవ్వబడుతుంది. 1 మరియు n మధ్య సంఖ్యలను ముద్రించడం మా పని నిఘంటువు ఆర్డర్.

ఉదాహరణ

n=13
[1 10 11 12 13 2 3 4 5 6 7 8 9]

వివరణ: మేము 1-13 మధ్య సంఖ్యలను లెక్సికోగ్రాఫికల్ క్రమంలో ముద్రించవలసి ఉన్నందున, సంఖ్యలు [1 10 11 12 13 2 3 4 5 6 7 8 9].

లెక్సికోగ్రాఫికల్ నంబర్స్ లీట్కోడ్ సొల్యూషన్ కోసం బ్రూట్ ఫోర్స్ అప్రోచ్

సమస్యను పరిష్కరించడానికి బ్రూట్ ఫోర్స్ విధానం క్రింది విధంగా ఉంది:

  1. 1 నుండి n మధ్య ఉన్న అన్ని సానుకూల పూర్ణాంక సంఖ్యలను తీగలుగా మార్చండి.
  2. ఇప్పుడు, తీగలను క్రమబద్ధీకరించండి. ఇది లెక్సిగ్రాఫికల్ క్రమంలో సంఖ్యలను అమర్చుతుంది.
  3. ఇప్పుడు క్రమబద్ధీకరించిన తీగలను మళ్ళీ పూర్ణాంకాలుగా మార్చండి మరియు ఇది ఫలితాన్ని ఇస్తుంది.

అమలు

లెక్సికోగ్రాఫికల్ సంఖ్యల కోసం సి ++ కోడ్

#include <bits/stdc++.h> 
using namespace std; 
    vector<int> lexicalOrder(int n) {
        string a[n];
        for(int i=1;i<=n;i++)
            a[i-1]=to_string(i);
        sort(a,a+n);
        vector<int>ans;
        for(int i=1;i<=n;i++)
           ans.push_back(stoi(a[i-1]));
        return ans;
    }
int main() 
{ 
 int n=13;
 vector<int> ans=lexicalOrder(n);
 for(int i=0;i<n;i++)
 cout<<ans[i]<<" ";
 return 0;
}
[1 10 11 12 13 2 3 4 5 6 7 8 9]

లెక్సికోగ్రాఫికల్ సంఖ్యల కోసం జావా కోడ్

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static List<Integer> lexicalOrder(int n) {
                String[] a = new String[n];
        for(int i=1;i<=n;i++)
            a[i-1]=Integer.toString(i);
        Arrays.sort(a);
        List<Integer> ans=new ArrayList<Integer>();  
        for(int i=1;i<=n;i++)
           ans.add( Integer.parseInt(a[i-1]));
       
        return ans;
    }
  public static void main(String[] args) {
         int n=13;
          List<Integer> ans = new ArrayList<>(n);
         ans=lexicalOrder(n);
        System.out.println(Arrays.toString(ans.toArray()));
  }
}
[1 10 11 12 13 2 3 4 5 6 7 8 9]

లెక్సికోగ్రాఫికల్ సంఖ్యల సంక్లిష్టత విశ్లేషణ లీట్‌కోడ్ పరిష్కారం

సమయం సంక్లిష్టత

పై కోడ్ యొక్క సమయం సంక్లిష్టత O (nlogn) ఎందుకంటే మేము తీగలను n స్ట్రింగ్‌తో క్రమబద్ధీకరిస్తున్నాము. ఇక్కడ n ఇచ్చిన సంఖ్య.

స్థల సంక్లిష్టత

పై కోడ్ యొక్క స్థల సంక్లిష్టత O (1) ఎందుకంటే మేము జవాబును నిల్వ చేయడానికి వేరియబుల్ మాత్రమే ఉపయోగిస్తున్నాము.

లెక్సికోగ్రాఫికల్ నంబర్స్ లీట్‌కోడ్ సొల్యూషన్ కోసం DFS అప్రోచ్

ఆలోచన చాలా సులభం. ప్రతిసారీ మేము 1-9 నుండి ఒకే అంకెతో ప్రారంభించి, ఆ సంఖ్యలపై 0-9 నుండి n కంటే చిన్నదిగా ఉన్నంత వరకు జోడించడం కొనసాగించండి. కాబట్టి ఇది లోతు-మొదటి-శోధన అల్గోరిథం వలె ఉంటుంది.

కాబట్టి మేము 1 తో ప్రారంభిస్తాము మరియు అది చిన్నది లేదా n కి సమానమైనంతవరకు దాని కోసం DFS ను చేస్తుంది.

మేము 9 వరకు అన్ని అంకెలకు వీటిని పునరావృతం చేస్తాము, ఆపై DFS ఫలితాన్ని నిల్వ చేసి ప్రింట్ చేస్తాము.

లెక్సికోగ్రాఫికల్ నంబర్లు లీట్‌కోడ్ సొల్యూషన్

అమలు

లెక్సికోగ్రాఫికల్ సంఖ్యల కోసం సి ++ కోడ్

#include <bits/stdc++.h> 
using namespace std; 
        void dfs(int cur, int n, std::vector<int>& ret)
    {
        if (cur <= n)
        {
            ret.push_back(cur);
            for (int i = 0; i <= 9; ++i)
            {
                dfs(cur*10+i, n, ret);
            }
        }
    }
    vector<int> lexicalOrder(int n) {
        vector<int> ret;
        for (int i = 1; i <= 9; ++i)
        {
            dfs(i, n, ret);
        }
        return ret;
        
    }

int main() 
{ 
 int n=13;
 vector<int> ans=lexicalOrder(n);
 for(int i=0;i<n;i++)
 cout<<ans[i]<<" ";
 return 0;
}
[1 10 11 12 13 2 3 4 5 6 7 8 9]

లెక్సికోగ్రాఫికల్ సంఖ్యల కోసం జావా కోడ్

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        for(int i=1;i<10;++i){
          dfs(i, n, res); 
        }
        return res;
    }
    
    public static void dfs(int cur, int n, List<Integer> res){
        if(cur>n)
            return;
        else{
            res.add(cur);
            for(int i=0;i<10;++i){
                if(10*cur+i>n)
                    return;
                dfs(10*cur+i, n, res);
            }
        }
    }
  public static void main(String[] args) {
         int n=13;
          List<Integer> ans = new ArrayList<>(n);
         ans=lexicalOrder(n);
        System.out.println(Arrays.toString(ans.toArray()));
  }
}
[1 10 11 12 13 2 3 4 5 6 7 8 9]

లెక్సికోగ్రాఫికల్ సంఖ్యల సంక్లిష్టత విశ్లేషణ లీట్‌కోడ్ పరిష్కారం

సమయం సంక్లిష్టత

పై కోడ్ యొక్క సమయం సంక్లిష్టత పై) ఎందుకంటే మేము మూలకాలను ఒక్కసారి మాత్రమే ప్రయాణిస్తున్నాము. ఇక్కడ n ఇచ్చిన విలువ.

స్థల సంక్లిష్టత

పై కోడ్ యొక్క స్థల సంక్లిష్టత O (లాగ్ (h)) ఎందుకంటే మేము DFS ఉపయోగిస్తున్నాము. ఇక్కడ h అనేది DFS చెట్టు యొక్క ఎత్తు.

ప్రస్తావనలు