leetcode之Permutations问题

蔚落 2022-07-11 12:06 101阅读 0赞

#include<vector>
    #include<iostream>
    using namespace std;
    class Solution {
    public:
    	vector<vector<int>> permute(vector<int>& nums);
    };
    int fractorial(int N)
    {
    	return N == 1 || N == 0 ? 1 : N*fractorial(N - 1);
    }
    void next_index(vector<int> &index, vector<int> &bounds)
    {
    	int i = index.size() - 1;
    	while (i >= 0)
    	{
    		if (index[i]<bounds[i])
    		{
    			++index[i];
    			break;
    		}
    		else
    		{
    			index[i] = 0;
    			--i;
    		}
    	}
    }
    vector<vector<int>> Solution::permute(vector<int>& nums) {
    	int N = nums.size();
    	vector<vector<int>> res;
    	vector<int> ori_nums = nums;
    	vector<int> index(N, 0);
    	vector<int> tmp = nums;
    	vector<int> bounds(N);
    	for (int i = 0; i<N; ++i)
    	{
    		bounds[i] = N - 1 - i;
    	}
    	for (int i = 0; i<fractorial(N); ++i)
    	{
    		nums = ori_nums;
    		for (int j = 0; j<N; ++j)
    		{
    			tmp[j] = nums[index[j]];
    			nums.erase(nums.begin() + index[j]);
    		}
    		res.push_back(tmp);
    		next_index(index, bounds);
    	}
    	return res;
    }
    void print_vector(vector<vector<int>> &nums)
    {
    	for (vector<vector<int>>::iterator iter1 = nums.begin(); iter1 != nums.end(); ++iter1)
    	{
    		for (vector<int> ::iterator iter2 = (*iter1).begin(); iter2 != (*iter1).end(); ++iter2)
    		{
    			cout << *iter2 << " ";
    		}
    		cout << endl;
    	}
    }
    int main()
    {
    	Solution s;
    	int arr[] = { 1, 3, 2 };
    	vector<int> nums;
    	for (int i = 0; i < sizeof(arr) / sizeof(int); ++i)
    	{
    		nums.push_back(arr[i]);
    	}
    	vector<vector<int>> res = s.permute(nums);
    	print_vector(res);
    	system("pause");
    }