2017-04-17 16:43:03 +0000   |     algorithm leetcode array   |   Viewed times   |    

主要收获

有一类问题是要靠数学抽象之后,推算出来的。

题目

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):

"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.

真的转k次,

假设初始数字为12345k=5。就真的把12345转4次,然后返回结果。

12345
12354
12435
12453
12534 <-- k=5
12543

每次转的代价是,转k次,复杂度为

代码

public class Solution {
    public String getPermutation(int n, int k) {
        char[] array = new char[n];
        for (int i = 0; i < n; i++) {
            array[i] = (char)('0'+i+1);
        }
        for (int i = 1; i < k; i++) {
            rotate(array);
        }
        return new String(array);
    }
    public void rotate(char[] array) {
        char c = Character.MIN_VALUE;
        int target = -1;
        for (int i = array.length-1; i >= 0; i--) {
            if (array[i] < c) {
                target = i;
                break;
            } else {
                c = array[i];
            }
        }
        if (target != -1) {
            for (int i = array.length-1; i > target; i--) {
                if (array[i] > array[target]) {
                    char temp = array[target];
                    array[target] = array[i];
                    array[i] = temp;
                    break;
                }
            }
        }
        for (int start = target+1, end = array.length-1; start < end; start++,end--) {
            char temp = array[start];
            array[start] = array[end];
            array[end] = temp;
        }
    }
}

结果

虽然过了,但挺凄惨的。 permutation-sequence-1

数学公式计算出结果

其实不用真的转这么多次。可以利用规律算出来结果。观察[1,2,3,4,5]的前30次转动的结果,

1  12345
2  12354
3  12435
4  12453
5  12534
6  12543
7  13245 #第7次,第二个数变3
8  13254
9  13425
10 13452
11 13524
12 13542
13 14235 #第13次,第二个数变4
14 14253
15 14325
16 14352
17 14523
18 14532
19 15234 #第19次,第二个数变5
20 15243
21 15324
22 15342
23 15423
24 15432
25 21345 # 第25次,2开头,第二个数变回1
26 21354
27 21435
28 21453
29 21534
30 21543
31 23145 #第31次,第二个数变3
32 23415
33 23451
34 23514

规律是因为4的阶乘4! = 4*3*2*1 = 24。所以高位万位,每24次加1.

3的阶乘3! = 3*2*1 = 6。所以高位千位,每6次加1.

代码

public class Solution {
    public String getPermutation(int n, int k) {
        List<Character> nums = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            nums.add((char)(i+'0'));
        }
        char[] res = new char[n];
        int period; // 循环周期,5位数的话,首位数的循环周期就是[5-0-1]!,就是4的阶乘,等于24
        k--; // 调整序数,题目是从1开始
        for (int index = 0; index < n; index++) {
            period = 1;
            for (int i = n - index - 1; i > 0; i--) {
                period *= i;
            }
            res[index] = nums.remove(k/period);
            k = k % period;
        }
        return new String(res);
    }
}

结果

permutation-sequence-2