atlasworld's blog

By atlasworld, history, 5 years ago, In English

Hello! We are given an integer N, The set [1,2,3,…,N] contains a total of N! unique permutations.

By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3 ) :

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

For example, given n = 3, k = 4, ans = "231"

if n = 11, k = 1, ans = "1234567891011"

In this case, k will be a positive integer that is less than INT_MAX. n is reasonable enough to make sure the answer does not bloat up a lot.

N can be upto 1000 , k can be upto 1000.

How to solve it, simple backtracking will time out after N>10.

  • Vote: I like it
  • -12
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but when we concatenate 10 and 11 it will be 1011 i.e 1,0,1,1. how to do for numbers?

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Apply the algorithm for a vector<int> not string.