算法
枚举每个位置上放哪个数 二进制优化
时间复杂度: O(n!)
空间复杂度: O(n)
没有二进制优化的时间复杂度: O(n^n)
常见时间复杂度从小到大排序(一般情况):
O(1) < O(log(n)) < O(n) < O(n*log(n)) < O(n^2) < O(n^3) < O(n) < O(2^n) < O(n!) < O(n^n)
因为这道题求全排列,所以时间复杂度最少是O(n!)
C++代码
class Solution {
public:
static vector<vector<int>> permute(const vector<int> &nums) {
vector<vector<int>> res;
if (nums.empty()) {
return res;
}
const int n = static_cast<int>(nums.size());
vector<int> path(n);
permuteDfs(nums, 0, path, 0, res);
return res;
}
private:
static void permuteDfs(const vector<int> &nums, const int numIndexVisited, //
vector<int> &path, const int pathIndex, vector<vector<int>> &res) {
const int n = static_cast<int>(path.size());
if (pathIndex == n) {
res.push_back(path);
return;
}
// 取所有的空位
int numIndexVisitedBis = (~numIndexVisited) & ((1 << n) - 1);
while (numIndexVisitedBis) {
// 取最低位的1
const int numIndexVisitedBit = numIndexVisitedBis & (-numIndexVisitedBis);
const int bit1 = numIndexVisitedBit - 1;
const int numIndex = bitCountArr[(bit1 >> 24) & 0xff] + bitCountArr[(bit1 >> 16) & 0xff] +
bitCountArr[(bit1 >> 8) & 0xff] + bitCountArr[bit1 & 0xff];
path[pathIndex] = nums[numIndex];
permuteDfs(nums, numIndexVisited | numIndexVisitedBit, path, pathIndex + 1, res);
// 清除最低位的1
numIndexVisitedBis &= numIndexVisitedBis - 1;
}
}
static int bitCount(int n) {
int cnt = 0;
for (; n; n &= n - 1) {
++cnt;
}
return cnt;
}
static array<int, 256> staticInitBitCountArr() {
array<int, 256> bitCountArr;
const int n = static_cast<int>(bitCountArr.size());
for (int i = 0; i < n; ++i) {
const int bitCnt = bitCount(i);
bitCountArr[i] = bitCnt;
}
return bitCountArr;
}
static const array<int, 256> bitCountArr;
};
const array<int, 256> Solution::bitCountArr = Solution::staticInitBitCountArr();
Java代码
Python3代码