leetcode/46ZPermutations

46ZPermutations

给定一个整数数组集合, 返回所有的数组排列可能

my solution (16ms)

如果单纯想要做出来, 很简单, 递归就完事了

static const int _ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    return 0;
}();

class Solution {
public:
    vector<vector<int>> permute(vector<int>& v) {
        size_t size = v.size(); 
        if (size == 1) return {v};
        else if (size == 0) return {};

        // asume size >= 2;
        for (int i = 0; i < size; ++i) {
            vector<int> temp = v;
            temp.erase(temp.begin() + i);

            permute_do({v[i]}, temp);
        }

        return ret;
    }

private:
    void permute_do(vector<int> curv, vector<int> v) {
        size_t size = v.size();

        if (size == 1) {
            ret.push_back(curv);
            ret.back().push_back(v.front());

            return;
        }

        for (int i = 0; i < size; ++i) {
            vector<int> tempV = v;
            tempV.erase(tempV.begin() + i);
            vector<int> tempCurv = curv;
            tempCurv.push_back(v[i]);

            permute_do(tempCurv, tempV);
        }
    }

private:
    vector<vector<int>> ret;
};

内存使用率应该很高, 因为每一次递归都会重新创建临时对象

但是想不到什么好的方式在不影响速度的情况下解决这个问题…

emmm, 内存使用果然很高…

(这个问题是几个月之前尝试过的, 试了 3 次没有成功, 今天一次就成功了,

而且解题的时间也挺短的, 看来进步还不错)

the best solution (14ms)

看一下最好的算法是怎么解决这个问题的

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > result;

        permuteRecursive(num, 0, result);
        return result;
    }

    // permute num[begin..end]
    // invariant: num[0..begin-1] have been fixed/permuted
    void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result)	{
        if (begin >= num.size()) {
            // one permutation instance
            result.push_back(num);
            return;
        }

        for (int i = begin; i < num.size(); i++) {
            swap(num[begin], num[i]);
            permuteRecursive(num, begin + 1, result);
            // reset
            swap(num[begin], num[i]);
        }
    }
};

他将 permute 中的循环合并到了 permuteRecursive 里面

核心在于 swap, 通过交换, 这样 result 就始终只有一个, 取而代之的是多了一个 int 参数传递