LeetCode 45 Permutations
1968 ワード
Given a collection of numbers、return all possible permuttions.
For example,
考え方:辞書の序文を使って、考え方は分かります。http://blog.csdn.net/mlweixiao/article/details/38893507このように、重複した数字があるかどうかに関わらず、処理できます。
For example,
[1,2,3]
have the follwing permuttions:[1,2,3]
、 [1,3,2]
、 [2,1,3]
、 [2,3,1]
、 [3,1,2]
、and [3,2,1]
.考え方:辞書の序文を使って、考え方は分かります。http://blog.csdn.net/mlweixiao/article/details/38893507このように、重複した数字があるかどうかに関わらず、処理できます。
public class Solution {
private void nextPermutation(int[] num) {
int i;
int cur = -1;
int temp;
// find the last increase sequence
for (i = num.length - 1; i >= 1; i--) {
if (num[i] > num[i - 1]) {
cur = i - 1;
break;
}
}
// if the increase sequence exists,
// swap the cur and the last one(bigger than it)
if (cur != -1) {
for (i = num.length - 1; i > cur; i--) {
if (num[i] > num[cur]) {
temp = num[cur];
num[cur] = num[i];
num[i] = temp;
break;
}
}
}
for (i = cur + 1; 2 * i <= cur + num.length - 1; i++) {
temp = num[i];
num[i] = num[num.length - i + cur];
num[num.length - i + cur] = temp;
}
}
@SuppressWarnings({ "rawtypes", "unchecked" })
public List> permute(int[] num) {
Arrays.sort(num);
int[] temparray = new int[num.length];
System.arraycopy(num, 0, temparray, 0, num.length);
ArrayList> result = new ArrayList>();
for (;;) {
List list = new ArrayList();
// list.addAll(Arrays.asList(num));
// Collection.addAll(list ,num);
// Arrays.asList() java.util.Arrays$ArrayList,
// ArrayList。Arrays$ArrayList ArrayList AbstractList,
//remove,add method AbstractList throw
// UnsupportedOperationException 。
//
for (int i = 0; i < num.length; i++) {
list.add(num[i]);
}
result.add(list);
nextPermutation(num);
if (Arrays.equals(num, temparray))
break;
}
return result;
}
}