一组数据的全排列II

问题描述

上期解决的问题是：int[] nums数组，数组中没有重复的数字，求这些数字组成的所有排列。

这次难度升级，nums数组中有重复的数字。

例如：

输入：[3,0,3,0]

输出：[[0, 0, 3, 3], [0, 3, 0, 3], [0, 3, 3, 0], [3, 0, 0, 3], [3, 0, 3, 0], [3, 3, 0, 0]]

问题分析

当nums数组中没有重复数字的时候，我们在考虑一个排列中的1个位置时，只需要判定该位置还有哪些数字可以放置进去就行了，也就是把已经使用过的数据除外就行。但现在不一样了，有重复数字，像例子中[3,0,3,0]，2个3，2个0，为了区分，我们从左往右，依次记作3(a)，0(a)，3(b)，0(b)，那么，现在的问题来了，我们将3(a)与3(b)交换位置，0(a)与0(b)交换位置，这个排列是完全没有变化的，还是同一个排列，但它却并不违反规则，我们并没有把一个数字重复使用，而且一个排列中的每个位置，也的确有放置不同数字的权利(我们可以从逻辑上认为这2个3和2个0是不同的），但是只看结果的话，当有重复数字出现的时候，得出的结果集中，将必然会出现重复的排列，若用上期的算法来计算[3,0,3,0]，得到的结果将会是下面这样：

[[3, 0, 0, 3], [3, 0, 3, 0], [3, 0, 0, 3], [3, 0, 3, 0], [3, 3, 0, 0],

[3, 3, 0, 0], [0, 3, 0, 3],[0, 3, 3, 0], [0, 0, 3, 3],[0, 0, 3, 3],

[0, 3, 3, 0], [0, 3, 0, 3], [0, 3, 0, 3], [0, 3, 3, 0],[0, 0, 3, 3],

[0, 0, 3, 3], [0, 3, 3, 0], [0, 3, 0, 3],[3, 3, 0, 0], [3, 3, 0, 0],

[3, 0, 3, 0],[3, 0, 0, 3], [3, 0, 3, 0], [3, 0, 0, 3]]

那么怎么解决有重复数字，造成的结果集中出现重复排列的问题呢？思路其实说起来很简单，就一句话：避免交换相等的数字的位置。考虑2个位置交换相等的数字，的确复杂了些，我们换个思路，只考虑一个排列中的1个位置，也就是，只要1个位置中的放置过的数字不与和它相等的数字交换，就能保证任意2个位置不会交换相等的数字了，对吧。你再仔细体会一下，比如第1个位置，放置过0(a)，在以后的决策中，就绝不能再放置0(b)，这样就能杜绝出现重复的排列。

好了，1个位置能够放置的数字有很多，为了判断待选数字是否曾经放置过，难道我们要把1个位置的的全部过往都记录下来，留待查验吗？这显然不够高效。但是，如果重复出现的数字，都是挨着出现就不一样啦，这样就只用把待选数字与当前位置放置的数字作对比就好了，相等则继续判断下一个待选数字，不相等才有机会放置进来，所以，我们要对nums数组作个预处理，排序，让重复的数字全都挨在一起，每个位置对于重复的数字，只能放一个进去。好啦，思路已经分析完了，如果还是不明白，就再多看几遍，下面是具体的代码实现，代码中关键地方也都加了注释。

代码实现

@Test

public voidtestPermuteII() {

int[] nums={3,,3,};

newSolution().permuteII(nums);

}

classSolution {

privateList

>result

=newLinkedList();

private intlength;

private int[]arr;

private boolean[]visit;

publicList

> permuteII(int[] nums) {

if(nums ==null|| nums.length==){

returnCollections.emptyList();

}

length= nums.length;

//先作个排序，为后面给排列去重做准备

Arrays.sort(nums);

arr= nums;

visit=new boolean[length];

generate(newLinkedList());

System.out.println("result: "+result);

returnresult;

}

private voidgenerate(List temp){

//找到了一个排列，加入到结果集中

if(temp.size() ==length){

/**

* 由于temp是不断变化的，加入到结果集时，

* 需要对temp进行深度复制

*/

result.add(newLinkedList(temp));

return;

}

//用于标记当前位置是否找到了合适的数字

booleanaccept =false;

intflag=;

for(inti=; i

/**

* 待选数字与当前位置放置的数字相等时，

* 直接忽略，避免出现重复的排列

*/

if(accept &&arr[i] == flag){

continue;

}

if(!visit[i]) {

accept =true;

//存储当前位置放置的数字

flag =arr[i];

temp.add(arr[i]);

visit[i] =true;

//进入下一个位置的决策

generate(temp);

//回溯

temp.remove(temp.size() -1);

visit[i] =false;

}

}

}

}