[プログラマー]並び方(JAVA)

1247 ワード
アルゴリズム#アルゴリズム# プログラマ テキストリンク
問題の説明
n人が一列に並んでいます.n人の番号は1番からn番までです.n個人で並ぶ方法はいろいろあります.たとえば、3人がいる場合は、次の6つの方法があります.
[1, 2, 3][1, 3, 2]
[2, 1, 3][2, 3, 1]
[3, 1, 2][3, 2, 1]
人の数nと自然数kが与えられた場合、予め順番に人を列挙する方法を完了した場合、k回の方法の解関数を返します.
せいげんじょうけん
nは20未満の自然数である.
kはnだ!以下は自然数です.
Code
import java.util.*;
class Solution {
    public int[] solution(int n, long k) {
        int[] ret = new int[n];
		List<Integer> list = new ArrayList<>();
        long num=1;
        int idx=0;
		for(int x=1 ; x<=n ; x++) {
			list.add(x);
			num *= x;
		}
        k--;
        while(idx<ret.length) {
        	num /= (n--);
        	int i = (int)(k/num);
        	ret[idx++] = list.get(i);
        	list.remove(i);
        	k %= num;
        }
        return ret;
    }
}
Comment
ルールさえ見つければ簡単に解決できる問題だ.
1.kは順番なので、サイズを維持し続けます.
2.次のような順序で入力された索引.
順序/配列/残りの数値に配置するインデックス
1 : 1 2 3 4 | 0 0 0 0
2 : 1 2 4 3 | 0 0 1 0
3 : 1 3 2 4 | 0 1 0 0
4 : 1 3 4 2 | 0 1 1 0
5 : 1 4 2 3 | 0 2 0 0
6 : 1 4 3 2 | 0 2 1 0
7 : 2 1 3 4 | 1 0 0 0
8 : 2 1 4 3 | 1 0 1 0
BOJ/IMplementation/グループ単語checker/Python
CSSシリーズ:パート10 -特異性