Lexicographical Numbers Leetcode 솔루션


난이도 중급
자주 묻는 질문 ByteDance
깊이 우선 검색

문제 설명

”Lexicographical Numbers”문제에서 우리는 숫자 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]입니다.

Lexicographical Numbers Leetcode 솔루션에 대한 무차별 대입 접근 방식

문제를 해결하기위한 무차별 대입 접근 방식은 다음과 같습니다.

  1. 1에서 n 사이의 모든 양의 정수를 문자열로 변환합니다.
  2. 이제 문자열을 정렬하십시오. 이렇게하면 사전 순으로 번호가 정렬됩니다.
  3. 이제 정렬 된 문자열을 다시 정수로 변환하면 결과가 제공됩니다.

실시

사전 숫자 용 C ++ 코드

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

사전 숫자 용 Java 코드

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]

Lexicographical Numbers Leetcode 솔루션의 복잡성 분석

시간 복잡성

위 코드의 시간 복잡성은 O (nlogn) n 문자열로 문자열을 정렬하기 때문입니다. 여기서 n은 주어진 숫자입니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (1) 답을 저장하는 데 변수 만 사용하고 있기 때문입니다.

Lexicographical Numbers Leetcode 솔루션에 대한 DFS 접근 방식

아이디어는 매우 간단합니다. 우리가 1-9의 한 자리로 시작할 때마다 그 숫자에 n보다 작은 한 0-9의 숫자를 계속 추가합니다. 따라서 이것은 Depth-First-Search 알고리즘과 정확히 동일합니다.

따라서 1부터 시작하여 n보다 작거나 같은 한 DFS를 수행합니다.

9까지 모든 자릿수에 대해이를 반복 한 다음 DFS 결과를 저장하고 인쇄합니다.

Lexicographical Numbers Leetcode 솔루션

실시

사전 숫자 용 C ++ 코드

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

사전 숫자 용 Java 코드

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]

Lexicographical Numbers Leetcode 솔루션의 복잡성 분석

시간 복잡성

위 코드의 시간 복잡성은 O (N) 요소를 한 번만 탐색하기 때문입니다. 여기서 n은 주어진 값입니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (로그 (h)) DFS를 사용하고 있기 때문입니다. 여기서 h는 DFS 트리의 높이입니다.

참조