【LeetCode】Permutations & Permutations II & Next Permutations & Permutation Sequence

这里对这四个关于排列的问题进行统一分析。这四个问题有共性也有区别的。

Permutations

参考链接

题目描述 

Given a collection of numbers, return all possible permutations.

For example,

[1,2,3]

 have the following permutations:

[1,2,3]

, 

[1,3,2]

, 

[2,1,3]

, 

[2,3,1]

, 

[3,1,2]

, and 

[3,2,1]

.

关键是明白其中的交换是意思

代码示例

class Solution {
public:
void get(vector<int> &num, int index, vector<vector<int > > &solution)
	{
		if(index >= num.size())
		{
			solution.push_back(num);
			return;
		}else
			for(int i = index; i < num.size(); i++)
			{
				swap(num[index],num[i]);
				get(num,index+1,solution);
				swap(num[index],num[i]);
			}
	}
	vector<vector<int > > permute(vector<int> &num) {
        // Note: The Solution object is instantiated only once.
        vector<vector<int > > solution;
		if(num.size()<1)return solution;
		get(num, 0, solution);
		return solution;
    }
};
           

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]

, and 

[2,1,1]

.

思路：这里需要注意几个排序的地方。 除了下面代码的思路还有几个思路： 思路一：做一个结果到次数的map，在添加一个新的结果前先查找一下这个结果是否已经存在，如果存在就不添加 思路二：在交换之前判断一个准备交换的数字是否已经交换过了。

代码示例

class Solution {
public:
    void internalpermuteUnique(vector<int> &num, int index,  vector<vector<int> > &result) {
        int size = num.size();
        
        if (size == index) {
            result.push_back(num);
        }
        else {
            for (int i = index; i < size; ++i) {
                if ((i > index) && (num[i] == num[index])) 
                  continue;
                else 
                  swap(num[index], num[i]);
                internalpermuteUnique(num, index + 1, result);
            }
            sort(num.begin() + index, num.end());
        }
    }
    
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > result;
        sort(num.begin(), num.end());
        internalpermuteUnique(num, 0, result);
        return result;
    }
};
           
       

Next Permutation

参考链接

题目描述 

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3

 → 

1,3,2

3,2,1

 → 

1,2,3

1,1,5

 → 

1,5,1

思路：先从后面找到一第一个num[i] < num[i+1] 的点，然后再把第i个数据和从尾到i第一个比num[i]大的数交换位置。然后再把i后面的做一下反序就可以了。

代码示例

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        int size = num.size();
        if(size < 2)	return;
        int i = 0, j = 0;         
        //找到第i个点。在i之后都是降序排列面 num[i]<num[i+1] 
		for(i = size -2;i>=0;i--)
        	if(num[i] < num[i+1])
        		break;
		if(i == -1)//说明整个数组是降序排列的，所以直接把数组反序即可
			reverse(num.begin(),num.end()); 
		else
		{//从尾向前找，找到第一个比num[i]大的数，然后和num[i]交换即可得所需序列 
			for(j = size - 1;j>i;j--)
				if(num[i] < num[j])
        			break;
 			swap(num[i],num[j]);//这个时候要从i+1到n是降序排列这时需要把后面的全部反序一下
			reverse(num.begin()+i+1,num.end()) ;
		}
    }
};
           

Permutation Sequence

参考链接

http://blog.csdn.net/doc_sgl/article/details/12840715

题目描述

The set 

[1,2,3,…,n]

 contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,

We get the following sequence (ie, for n = 3):

1. "123"

2. "132"

3. "213"

4. "231"

5. "312"

6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

思路：

在n!个排列中，第一位的元素总是(n-1)!一组出现的，也就说如果p = k / (n-1)!，那么排列的最开始一个元素一定是nums[p]。

假设有n个元素，第K个permutation是

a1, a2, a3, .....   ..., an

那么a1是哪一个数字呢？

那么这里，我们把a1去掉，那么剩下的permutation为

a2, a3, .... .... an, 共计n-1个元素。 n-1个元素共有(n-1)!组排列，那么这里就可以知道

设变量K1 =K-1

a1 = K1 / (n-1)!

同理，a2的值可以推导为

K2 = K1 % (n-1)!

a2 = K2 / (n-2)!

 .......

K(n-1) = K(n-2) /2!

a(n-1) = K(n-1) / 1!

an = K(n-1)

下面代码中，一个关键的地方就是

for(int j = selected; j < n-i-1; j++)
                nums[j] = nums[j+1];
           

就是哪个数字使用过了，就从数组里去除。

代码示例

class Solution {
public:
   string getPermutation(int n, int k) {
        vector<int> nums(n);
        int pCount = 1;
        for(int i = 0 ; i < n; ++i) {
            nums[i] = i + 1;
            pCount *= (i + 1);
        }

        k--;
		string res = "";
        for(int i = 0 ; i < n; i++) {
			pCount = pCount/(n-i);
            int selected = k / pCount;
			res += ('0' + nums[selected]);
            
            for(int j = selected; j < n-i-1; j++)
                nums[j] = nums[j+1];
            k = k % pCount;
        }
        return res;
    }
};
           

推荐学习C++的资料

C++标准函数库 http://download.csdn.net/detail/chinasnowwolf/7108919

在线C++API查询 http://www.cplusplus.com/ map使用方法 http://www.cplusplus.com/reference/map/map/

queue使用方法 http://www.cplusplus.com/reference/queue/queue/

vector使用方法

http://www.cplusplus.com/reference/vector/vector/