• 全排列
• 带重复元素的排列
• 下一个排列
• 上一个排列
• 第 k 个排列
• 排列序号
• 排列序号II

全排列

[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

分析

Paste_Image.png

```class Solution {
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums == null)
return res;
if(nums.length == 0)
{
return res;
}

ArrayList<Integer> list = new ArrayList<>();
dfs(res, list, nums);
return res;
}

private void dfs(List<List<Integer>> res, ArrayList<Integer> list, int[] nums) {

int n = nums.length;
if(list.size() == n)
{
return;
}

for(int i = 0;i < n;i++) {
if(list.contains(nums[i]))
continue;
dfs(res, list, nums);
list.remove(list.size() - 1);
}
}
}```

```class Solution {
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if ( nums == null)
return res;
if( nums.length == 0)
{
return res;
}
List<Integer> list = new ArrayList<>();

for(int i=1;i<nums.length;i++) {
int size1 = res.size();
for(int j=0;j<size1;j++) {
int size2 = res.get(0).size();
for(int k=0;k<=size2;k++) {
ArrayList<Integer> temp = new ArrayList<>(res.get(0));
}
res.remove(0);
}
}
return res;
}
}```

Paste_Image.png

代码

```class Solution {
/**
* @param nums: A list of integers.
* @return: A list of unique permutations.
*/
public List<List<Integer>> permuteUnique(int[] nums) {

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

if(nums == null)
return null;

if(nums.length == 0)
{
return res;
}

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

//先将数组排序，这样相同元素将会出现在一起
Arrays.sort(nums);

int n = nums.length;
int[] visited = new int[n];
for(int i=0;i<n;i++)
visited[i] = 0;//0标识未访问

helper(res, list, visited, nums);
return res;
}

private void helper(ArrayList<List<Integer>> res, ArrayList<Integer> list, int[] visited, int[] nums) {

if(nums.length == list.size()) {
}

for(int i=0;i<nums.length;i++) {

if(visited[i] == 1 || i!= 0 && (visited[i-1] == 0 && nums[i] == nums[i-1]))
continue;
/*
上面的判断主要是为了去除重复元素影响。
比如，给出一个排好序的数组，[1,2,2]，那么第一个2和第二2如果在结果中互换位置，
我们也认为是同一种方案，所以我们强制要求相同的数字，原来排在前面的，在结果
当中也应该排在前面，这样就保证了唯一性。所以当前面的2还没有使用的时候，就
不应该让后面的2使用。
*/
visited[i] = 1;
helper(res, list, visited, nums);
list.remove(list.size()-1);
visited[i] = 0;

}

}
}```

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

分析

```public class Solution {
/**
* @param nums: an array of integers
* @return: return nothing (void), do not return anything, modify nums in-place instead
*/
public int[] nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i + 1] <= nums[i]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
return nums;
}

private void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}

private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}```

分析

```public class Solution {
/**
* @param nums: A list of integers
* @return: A list of integers that's previous permuation
*/
public void swapItem(ArrayList<Integer> nums, int i, int j) {
Integer tmp = nums.get(i);
nums.set(i, nums.get(j));
nums.set(j, tmp);
}
public void swapList(ArrayList<Integer> nums, int i, int j) {
while ( i < j) {
swapItem(nums, i, j);
i ++; j --;
}
}
public ArrayList<Integer> previousPermuation(ArrayList<Integer> nums) {
int len = nums.size();
if ( len <= 1)
return nums;
int i = len - 1;
while ( i > 0 && nums.get(i) >= nums.get(i-1) )
i --;
swapList(nums, i, len - 1);
if ( i != 0) {
int j = i;
while ( nums.get(j) >= nums.get(i-1) ) j++;
swapItem(nums, j, i-1);
}

return nums;
}
}```

第k个排列

1 ≤ n ≤ 9

123 132 213 231 312 321 如果 k = 4, 第4个排列为，231.

分析

X=an(n-1)!+an-1(n-2)!+...+ai(i-1)!+...+a21!+a1*0!

ai为整数，并且0<=ai<i(1<=i<=n)

N个数的第k个排序，例子，1，2，3，4共有4！种排列，1234,1243,1324等等。按顺序应该是

1234

1243

1324

1342

1423

1432等等

```class Solution {
/**
* @param n: n
* @param k: the kth permutation
* @return: return the k-th permutation
*/
public String getPermutation(int n, int k) {

StringBuilder sb = new StringBuilder();
boolean[] used = new boolean[n];

k = k - 1;
int factor = 1;
for (int i = 1; i < n; i++) {
factor *= i;
}

for (int i = 0; i < n; i++) {
int index = k / factor;
k = k % factor;
for (int j = 0; j < n; j++) {
if (used[j] == false) {
if (index == 0) {
used[j] = true;
sb.append((char) ('0' + j + 1));
break;
} else {
index--;
}
}
}
if (i < n - 1) {
factor = factor / (n - 1 - i);
}
}

return sb.toString();

}
}```

分析

```public class Solution {
/**
* @param A an integer array
* @return a long integer
*/
public long permutationIndex(int[] A) {
HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();

for (int i = 0; i < A.length; i++) {
if (hash.containsKey(A[i]))
hash.put(A[i], hash.get(A[i]) + 1);
else {
hash.put(A[i], 1);
}
}
long ans = 0;
for (int i = 0; i < A.length; i++) {
for (int j = i + 1; j < A.length; j++) {
if (A[j] < A[i]) {
hash.put(A[j], hash.get(A[j])-1);
ans += generateNum(hash);
hash.put(A[j], hash.get(A[j])+1);

}

}
hash.put(A[i], hash.get(A[i])-1);
}

return ans+1;
}

long fac(int numerator) {

long now = 1;
for (int i = 1; i <= numerator; i++) {
now *= (long) i;
}
return now;
}

long generateNum(HashMap<Integer, Integer> hash) {
long denominator = 1;
int sum = 0;
for (int val : hash.values()) {
if(val == 0 )
continue;
denominator *= fac(val);
sum += val;
}
if(sum==0) {
return sum;
}
return fac(sum) / denominator;
}
}```

分析

C(n-1) = (首元素为小于当前元素，之后的全排列值) P(1) = 1;

C(n-1) = (n-1)!/(A1!A2!···Aj!)k(其中Ai 为重复元素的个数，k为小于首元素前不重复的个数)

```/**
* @param A an integer array
* @return a long integer
*/
long fac(int numerator) {
long now = 1;
for (int i = 1; i <= numerator; i++) {
now *= (long) i;
}
return now;
}
long generateNum(HashMap<Integer, Integer> hash) {
long denominator = 1;
int sum = 0;
for (int val : hash.values()) {
if(val == 0 )
continue;
denominator *= fac(val);
sum += val;
}
if(sum==0) {
return sum;
}
return fac(sum) / denominator;
}

public long permutationIndexII(int[] A) {
HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();

for (int i = 0; i < A.length; i++) {
if (hash.containsKey(A[i]))
hash.put(A[i], hash.get(A[i]) + 1);
else {
hash.put(A[i], 1);
}
}
long ans = 0;
for (int i = 0; i < A.length; i++) {
HashMap<Integer, Integer> flag = new HashMap<Integer, Integer>();

for (int j = i + 1; j < A.length; j++) {
if (A[j] < A[i] && !flag.containsKey(A[j])) {
flag.put(A[j], 1);
hash.put(A[j], hash.get(A[j])-1);
ans += generateNum(hash);
hash.put(A[j], hash.get(A[j])+1);
}

}
hash.put(A[i], hash.get(A[i])-1);
}
return ans + 1;
}```

0 条评论

相关文章

40011

2016天梯模拟赛 进阶题解

L2-005 集合相似度 题目链接： https://www.patest.cn/contests/gplt/L2-005 题目的意思是要求两个集合的交集中...

4279

(3)TreeSet集合 A:底层数据结构是红黑树(是一个自平衡的二叉树) B:保证元素的排序方式 a:自然排序(元素具备比较性) 让元素所属的类实现C...

3256

java基础学习_集合类03_用户登录注册案例(集合版)、Set集合、Collection集合总结_day17总结

============================================================================= ==...

1022

java基础学习_集合类04_Map接口、Collections工具类_day18总结

============================================================================= ==...

781

唠唠SE的集合-01——Collection接口

682

Set接口 　　前面已经简绍过Set集合，它类似于一个罐子，一旦把对象'丢进'Set集合，集合里多个对象之间没有明显的顺序。Set集合与Collectio...

2899

2925