重生做网站的小说,网站开发的发展历史及趋势,哪个网站可以做电视背景墙,手机个人简历模板下载分析
给定一个可包含重复数字的序列 nums #xff0c;按任意顺序 返回所有不重复的全排列。 示例 1#xff1a; 输入#xff1a;nums [1,1,2] 输出#xff1a; [[1,1,2], [1,2,1], [2,1,1]]
题目
由于元素是重复的#xff0c;要求返回不重复的#xff0c;所以一定会有…分析
给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。 示例 1 输入nums [1,1,2] 输出 [[1,1,2], [1,2,1], [2,1,1]]
题目
由于元素是重复的要求返回不重复的所以一定会有剪枝的动作具体的思路就是给数组排序然后发现上一个元素和当前元素一样的话就没必要再遍历了。这里需要注意的是剪枝不能解决掉所有的重复元素的问题比如0,0,0,1,9这样的序列在第0个元素求解完以后递归求解第1个元素的时候由于俩个元素都是0所以肯定会发生重复所以这里可以再用一个set来存储全排序列
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;public class permutationsII {private static SetListInteger set new HashSet();public static void main(String[] args) {int[] arr {0,1,0,0,9};Arrays.sort(arr);getRank(arr,0,arr.length);ListListInteger res new ArrayList();res.addAll(set);for(ListInteger lis : res) {for(Integer data:lis) {System.out.print(data );}System.out.println();}}public static void getRank(int[] nums,int start,int len) {if(start 1 len) {ListInteger lis new ArrayList();for(int i 0;ilen;i) {lis.add(nums[i]);}set.add(lis);return;}for(int i start;ilen;i) {if(start i nums[i-1] nums[i]) {continue;}int tmp nums[start];nums[start] nums[i];nums[i] tmp;getRank(nums,start1,len);tmp nums[start];nums[start] nums[i];nums[i] tmp;}}
}
