本文主要是介绍144.Permutations II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[[1,1,2],[1,2,1],[2,1,1] ]分析：
相对于http://blog.csdn.net/u010339647/article/details/50594557的差别是本次输入的数组中可能有重复的数字。那么我怎么对这些包含重复的数字进行全排列呢？
之前介绍了求全排列的过程就是把当前beginIndex下标对应的数字与其后面的index(index需要从beginIndex自增到len-1)下标对应数字依次进行交换的过程。那么如果是对于包含重复数字的来说：
判断beginIndex字符需要与index下标对应的字符交换标准是在数组nums下标为[beiginIndex,index)中没有数字与nums[index]相等，如果存在则没有必要交换，假设nums[index]与nums[j]相等，j在[beiginIndex,index)之间，因为之前nums[beginIndex]已经与nums[j]交换了，则没有必要再让nums[beginIndex]与nums[index]再进行交换了，因为交换之后得到的全排列会和之前的结果完全重复。
比如对于abcdbef,当a与第一个b交换之后，后面的字符为acdbef的全排列，那么a就没有必要与第二个b交换了，因为交换之后后面的字符还是acdbef的全排列。
IList<IList<int>> result = new List<IList<int>>();public IList<IList<int>> PermuteUnique(int[] nums){if (nums.Length > 0){Permutation(nums, 0);}return result;}/** nums 表示待排序的字符数组* beginIndex表示开始全排列的下标*/public void Permutation(int[] nums, int beginIndex){int len = nums.Length;/** 说明排序到了最后一个字符，则可以把目前的字符数组转化为字符串加入到最后的结果中* 这也是终止递归的条件。*/if (beginIndex == len - 1){IList<int> list = new List<int>(nums);result.Add(list);return;}/* * 如果当前开始排序的字符不是最后一个字符，则* 1.把这个字符与其后面的所有字符位置相互换；* 2.然后递归为开始全排列的下标为beginIndex+1；* 3.最后要把第一步中交换的两个字符拿回来，保证charArr还是初始的待排序的字符数组。* */else {//index对应的字符表示需要与beginIndex对应的下标交换的字符/* 1.把这个字符与其后面的所有字符位置相互换；*/for (int index = beginIndex; index < len;index++){if(isSwap(nums,beginIndex,index)){Swap(nums,beginIndex,index);/*2.然后递归为开始全排列的下标为beginIndex+1；*/Permutation(nums, beginIndex+1);/*3.最后要把第一步中交换的两个字符拿回来，保证nums还是初始的待排序的字符数组。*/Swap(nums,beginIndex,index);}}}}/*** 判断beginIndex字符是否需要与index下标对应的字符交换* 判断的标准是在数组nums下标为[beiginIndex,index)中有字符与nums[index]相等，如果存在则没有必要交换，假设nums[index]与nums[j]相等，* j在[beiginIndex,index)之间，因为之前nums[beginIndex]已经与nums[j]交换了，则没有必要再让nums[beginIndex]与nums[index]再进行交换了，因为交换之后* 得到的全排列会和之前的结果完全重复。* 比如对于abcdbef,当a与第一个b交换之后，后面的字符为acdbef的全排列，那么a就没有必要与第二个b交换了，因为交换之后后面的字符还是acdbef的全排列。*/private bool isSwap(int[] nums, int beginIndex, int index){for(int i=beginIndex;i<index;i++){if(nums[i] == nums[index]){return false;}}return true;}private void Swap(int[] nums, int i, int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
这篇关于144.Permutations II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
