लेक्सिकोग्राफिक नंबर लेटकोड सॉल्यूशन


कठिनाई स्तर मध्यम
में अक्सर पूछा ByteDance
गहराई पहली खोज

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

समस्या में "लेक्सिकोग्राफिक नंबर" हमें एक नंबर n दिया जाता है। हमारा काम 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]

लेक्सिकोग्राफिक नंबरों की जटिलता का विश्लेषण Leetcode Solution

समय की जटिलता

उपरोक्त कोड की समय जटिलता है ओ (nlogn) क्योंकि हम n स्ट्रिंग के साथ स्ट्रिंग्स को सॉर्ट कर रहे हैं। यहाँ n दी गई संख्या है।

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

उपरोक्त कोड की अंतरिक्ष जटिलता है ओ (1) क्योंकि हम उत्तर को संग्रहीत करने के लिए केवल एक चर का उपयोग कर रहे हैं।

डीएफएस दृष्टिकोण लेक्सोग्राफिक संख्याओं के लिए लेटकोड समाधान

विचार बहुत सरल है। हर बार जब हम 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]

लेक्सिकोग्राफिक नंबरों की जटिलता का विश्लेषण Leetcode Solution

समय की जटिलता

उपरोक्त कोड की समय जटिलता है पर) क्योंकि हम तत्वों को केवल एक बार ट्रेस कर रहे हैं। यहाँ n दिया गया मान है।

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

उपरोक्त कोड की अंतरिक्ष जटिलता है O (लॉग (h)) क्योंकि हम DFS का उपयोग कर रहे हैं। यहाँ h DFS पेड़ की ऊँचाई है।

संदर्भ