FilesExpand file tree

 master

/

PermutationSequence60.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

78 lines (73 loc) · 1.94 KB

 master

/

PermutationSequence60.java

Copy path

Top

File metadata and controls

• Code
• Blame

78 lines (73 loc) · 1.94 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

/**

* 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 for n = 3:

*

* "123"

* "132"

* "213"

* "231"

* "312"

* "321"

*

* Given n and k, return the kth permutation sequence.

*

* Note:

* Given n will be between 1 and 9 inclusive.

* Given k will be between 1 and n! inclusive.

*

* Example 1:

* Input: n = 3, k = 3

* Output: "213"

*

* Example 2:

* Input: n = 4, k = 9

* Output: "2314"

*/

public class PermutationSequence60 {

public String getPermutation(int n, int k) {

StringBuilder sb = new StringBuilder();

int[] count = new int[1];

boolean[] used = new boolean[n];

helper(sb, n, k, count, used);

return sb.toString();

}

private boolean helper(StringBuilder sb, int n, int k, int[] count, boolean[] used) {

if (sb.length() == n) {

count[0]++;

return count[0] == k;

}

for (int i=0; i<n; i++) {

if (used[i]) continue;

sb.append((char) (i + '1'));

used[i] = true;

if (helper(sb, n, k, count, used)) return true;

sb.deleteCharAt(sb.length() - 1);

used[i] = false;

}

return count[0] == k;

}

public String getPermutation2(int n, int k) {

int[] factors = new int[n];

List<Integer> list = new ArrayList<>();

for (int i=0; i<n; i++) {

if (i == 0) {

factors[0] = 1;

} else {

factors[i] = factors[i-1] * i;

}

list.add(i+1);

}

StringBuilder sb = new StringBuilder();

k--;

for (int i=n; i>0; i--) {

int idx = k / factors[i - 1];

k = k % factors[i - 1];

int val = list.get(idx);

list.remove(idx);

sb.append(val);

}

return sb.toString();

}

}