目录
无重复数的全排列问题
问题描述
思路分析
测试代码
有重复数的全排列问题
问题描述
思路分析
测试代码
下一个排列问题
问题描述
思路分析
测试代码
无重复数的全排列问题
问题描述
给定一个没有重复数字的序列，返回其所有可能的全排列。
输入: [1,2,3]
输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
思路分析
解决一个算法问题，我比较习惯于从基本的想法做起，我们先回顾一下我们自己是如何写一组数的全排列的：1，3，5，9（为了方便，下面我都用数进行全排列而不是字符）。 【1，3，5，9】（第一个） 首先保持第一个不变，对【3，5，9】进行全排列。 同样地，我们先保持3不变，对【5，9】进行全排列。 保持5不变，对9对进行全排列，由于9只有一个，它的排列只有一种：9。 故排列为【1，3，5，9】 接下来5不能以5打头了，5，9相互交换，得到 【1，3，9，5】 此时5，9的情况都写完了，不能以3打头了，得到
1，5，3，9
1，5，9，3
1，9，3，5
1，9，5，3
这样，我们就得到了1开头的所有排列，这是我们一般的排列数生成的过程。再接着是以3、5、9打头，得到全排列。
测试代码
public class Permute_46 {
static List<List<Integer>> lists=new ArrayList<>();
public static List<List<Integer>> permute(int[] nums) {
List<Integer> list=new ArrayList<>();
if(nums.length==0||nums==null){
return lists;
}
permute(nums,list,0);
return lists;
}
private static void permute(int[] nums, List<Integer> list, int index) {
//定义出口条件
if(index==nums.length){
lists.add(new ArrayList<>(list));
return;
}
//i是从开始 i=index ;swap(,i)index相当于固定当前位置，在进行下一位的排列。
for(int i=index;i<nums.length;i++){
swap(nums,index,i);
list.add(nums[index]);
permute(nums,list,index+1);
list.remove(list.size()-1);
swap(nums,index,i);
}
}
public static void main(String[] args){
int[] nums=new int[]{1,2,3};
List<List<Integer>> lists=new ArrayList<>();
lists=permute(nums);
for(List<Integer> list:lists){
for(int i:list){
System.out.print(i+" ");
}
System.out.println();
}
}
}
有重复数的全排列问题
问题描述
给定一个可包含重复数字的序列，返回所有不重复的全排列。
输入: [1,1,2]
输出: [ [1,1,2], [1,2,1], [2,1,1] ]
思路分析
这题和上面一题最主要的区别就是数字可以重复，如果按照原来的方法去做，肯定会出现重复的排列，那么我们要做的就是去重，这里我们先考虑一下，在前后交换的过程中，如果两个元素相同的话，就不应该让他们进行交换， 举个例子：对于序列<1,1,2,3>。在DFS首遍历时，1 作为首元素被加到list中，并进行后续元素的添加；那么，当DFS跑完第一个分支，遍历到1 (第二个)时，这个1 不再作为首元素添加到list中，因为1 作为首元素的情况已经在第一个分支中考虑过了，也就是说swap(num,0,1)这段代码不应该发生，因此改进的测试代码如下。
测试代码
public class Permute_47 {
static List<List<Integer>> lists=new ArrayList<>();
public static List<List<Integer>> permute2(int[] nums) {
List<Integer> list=new ArrayList<>();
if(nums.length==0||nums==null){
return lists;
}
permute(nums,list,0);
return lists;
}
private static void permute(int[] nums, List<Integer> list, int index) {
//定义出口条件
if(index==nums.length){
lists.add(new ArrayList<>(list));
return;
}
for(int i=index;i<nums.length;i++){
//当要交换的两个值是相等的时候，就停止
if(i!=index&&nums[i]==nums[index]){
continue;
}
swap(nums,index,i);
list.add(nums[index]);
permute(nums,list,index+1);
list.remove(list.size()-1);
swap(nums,index,i);
}
}
public static void main(String[] args){
int[] nums=new int[]{1,1,2,3};
List<List<Integer>> lists=new ArrayList<>();
lists=permute2(nums);
for(List<Integer> list:lists){
for(int i:list){
System.out.print(i+" ");
}
System.out.println();
}
}
}
下一个排列问题
问题描述
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1
思路分析
我的整个思路是这样的
1.从后往前找，依次比较nums[i]和nums[i+1],找到第一个nums[i]<nums[i+1]的数，要替换成一个比他大但最接近他的数
2.如何找到要替换的数？同样是从后往前遍历，因为在第一步我们已经知道从i位置往后是递减的， 所以我们从后往前找，找到第一个比num[i]大的数就是最接近num[i]的数
3.将第二步找到的数和num[i]进行替换，是不是这么一替换就完了呢？当然不是
4.由于i位置后面的数都是字典序最大的排列了，所以我们要将他换成最小的，这样才是下一个排列。
测试代码
public class NextPermutation_31 {
/*
思路（参考网上）：
1.从后往前找，依次比较nums[i]和nums[i+1],找到第一个nums[i]<nums[i+1]的数，要替换成一个比他大但最接近他的数
2.如何找到要替换的数？同样是从后往前遍历，因为在第一步我们已经知道从i位置往后是递减的，
所以我们从后往前找，找到第一个比num[i]大的数就是最接近他num[i]的数
3.将第二步找到的数和num[i]进行替换，是不是这么一替换就完了呢？当然不是
4.由于i位置后面的数都是字典序最大的排列了，所以我们要将他换成最小的，这样才是下一个排列。
*/
public static void nextPermutation(int[] nums) {
if(nums.length==0||nums==null){
return;
}
int i=nums.length-2;
while(i>=0&&nums[i]>=nums[i+1]){
i--;
}
//找到了第一个num[i]>num[i+1]的数
if(i>=0){ //如果这个i在数组中
int j=nums.length-1;
while(j>i&&nums[j]<=nums[i]){
j--;
}
swap(nums,i,j);
reverse(nums,i+1,nums.length-1);
}else{
//直接全部反序
reverse(nums,0,nums.length-1);
}
}
private static void reverse(int[] nums, int i, int j) {
//从i到j进行倒序
while(i<j){
swap(nums,i,j);
i++;
j--;
}
}
public static void swap(int[] nums,int i,int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
