【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/