目錄

• • 1、題目
  • 2、思考
  • 3、優(yōu)化

1、題目

給定一個(gè) 沒(méi)有重復(fù) 數(shù)字的序列，返回其所有可能的全排列。

2、思考

老規(guī)矩，先畫(huà)出給出的例子的解空間樹(shù)：

觀察我們可以發(fā)現(xiàn)：
1、深度向下一層深入時(shí)，出現(xiàn)過(guò)的元素不能再出現(xiàn)，我們能選擇的只有沒(méi)有選擇過(guò)的元素，此處我用的哈希法set。
2、結(jié)束條件是：同一個(gè)樹(shù)枝上的結(jié)點(diǎn)個(gè)數(shù)>=nums數(shù)組的size().
于是可以得到初步代碼：注意這里判斷元素是否出現(xiàn)過(guò)我用的set，后面會(huì)有優(yōu)化

class Solution { public:vector<vector<int>> result;vector<int> res;unordered_set<int> set;void backtracking(vector<int>& nums){//如果res元素個(gè)數(shù)和nums一樣多說(shuō)明一個(gè)排列已經(jīng)完成if(res.size() == nums.size()){result.push_back(res);return;}for(int i=0;i<nums.size();i++){//如果這個(gè)元素在剩下的元素中，處理結(jié)點(diǎn)if(set.find(nums[i])!=set.end()){//處理結(jié)點(diǎn)；set.erase(nums[i]);res.push_back(nums[i]);//遞歸,探索下一層backtracking(nums); //遞歸//回溯，撤銷(xiāo)處理結(jié)果res.pop_back();set.insert(nums[i]);}//如果這個(gè)元素已經(jīng)用過(guò)了，不做處理}return;}vector<vector<int>> permute(vector<int>& nums) {result.clear();res.clear();//裝載setfor(int i=0;i<nums.size();i++) set.insert(nums[i]);//開(kāi)始回溯backtracking(nums);return result;} };

很明顯因?yàn)轭l繁使用了set的插入操作，刪減操作。我的時(shí)間效率并不高。
接下來(lái)優(yōu)化一下。

3、優(yōu)化

這里判斷是否出現(xiàn)的內(nèi)容其實(shí)就是nums數(shù)組的元素。所以我們可以創(chuàng)建一個(gè)used數(shù)組，對(duì)應(yīng)這個(gè)nums數(shù)組。
used[i]一開(kāi)始為false，如果在res中壓入了nums[i]，那么我們就說(shuō)明這個(gè)數(shù)用過(guò)了。這時(shí)使used[i]=true；
再次遍歷的時(shí)候，如果used[i]=true；就跳過(guò)，說(shuō)明這個(gè)數(shù)已經(jīng)用過(guò)了。
下面是優(yōu)化代碼;

class Solution { public:vector<vector<int>> result;vector<int> res;vector<bool> used;void backtracking(vector<int>& nums){//如果res元素個(gè)數(shù)和nums一樣多說(shuō)明一個(gè)排列已經(jīng)完成if(res.size() == nums.size()){result.push_back(res);return;}for(int i=0;i<nums.size();i++){//如果這個(gè)元素在剩下的元素中，處理結(jié)點(diǎn)if(used[i] == false){//處理結(jié)點(diǎn)；used[i]=true;res.push_back(nums[i]);//遞歸,探索下一層backtracking(nums); //遞歸//回溯，撤銷(xiāo)處理結(jié)果res.pop_back();used[i]=false;}//如果這個(gè)元素已經(jīng)用過(guò)了，不做處理}return;}vector<vector<int>> permute(vector<int>& nums) {result.clear();res.clear();//裝載used數(shù)組for(int i=0;i<nums.size();i++) used.push_back(false);backtracking(nums);return result;} };

對(duì)比速度：

有很明顯的速度提升。

總結(jié)

以上是生活随笔為你收集整理的leetcode 46. 全排列 思考分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。