शब्दकोष क्रमांक लेटकोड सोल्यूशन


अडचण पातळी मध्यम
वारंवार विचारले बाइट डान्स
खोली प्रथम शोध

समस्या विधान

"शब्दकोष संख्या" या समस्येमध्ये आम्हाला एक क्रमांक दिला जातो. आमचे कार्य म्हणजे 1 आणि n मधील संख्या मुद्रित करणे शब्दावली ऑर्डर

उदाहरण

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

स्पष्टीकरण: आपल्याला शब्दकोष क्रमवारीत १ ते १ between दरम्यान अंक मुद्रित करायचे आहेत, संख्या [1 13 1 10 11 12 13 2 3 4 5 6 7] आहेत.

लेक्सकोग्राफिकल नंबर लीटकोड सोल्यूशनसाठी ब्रूट फोर्स अ‍ॅप्रोच

समस्येचे निराकरण करण्यासाठी क्रूर शक्ती दृष्टीकोन खालीलप्रमाणे आहे:

  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 स्ट्रिंगसह सॉर्ट करत आहोत. येथे एन दिलेली संख्या आहे.

जागेची जटिलता

वरील कोडची स्पेस कॉम्प्लेक्सिटी आहे ओ (1) कारण आम्ही उत्तर संग्रहित करण्यासाठी फक्त एक व्हेरिएबल वापरत आहोत.

डिक्शनोग्राफिक नंबर लेटकोड सोल्यूशनसाठी डीएफएस दृष्टीकोन

कल्पना अगदी सोपी आहे. प्रत्येक वेळी आम्ही 1-9 पासून एका अंकासह प्रारंभ करतो आणि नंतर त्या संख्येवर 0-9 पासून अंक जोपर्यंत तो एनपेक्षा लहान असतो तो जोडत रहा. हे अगदी खोली-प्रथम-शोध अल्गोरिदम सारखेच आहे.

तर आपण 1 ने सुरूवात करू आणि एन किंवा त्याइतकी लहान होईपर्यंत त्यासाठी डीएफएस करू.

आम्ही 9 पर्यंत सर्व अंकांसाठी याची पुनरावृत्ती करू आणि नंतर डीएफएस निकाल संग्रहित आणि मुद्रित करू.

शब्दकोष क्रमांक लेटकोड सोल्यूशन

अंमलबजावणी

शब्दकोष क्रमांकांसाठी सी ++ कोड

#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]

डिक्शनोग्राफिक नंबर लीटकोड सोल्यूशनचे जटिल विश्लेषण

वेळ गुंतागुंत

वरील कोडची वेळ जटिलता आहे O (n) कारण आम्ही घटकांचा एकदाच शोध घेत आहोत. येथे n दिलेली व्हॅल्यू आहे.

जागेची जटिलता

वरील कोडची स्पेस कॉम्प्लेक्सिटी आहे ओ (लॉग (एच)) कारण आम्ही डीएफएस वापरत आहोत. येथे एच डीएफएस झाडाची उंची आहे.

संदर्भ