当前位置: 首页 > news >正文

网站正在建设中模板免费下载短视频广告投放平台

网站正在建设中模板免费下载,短视频广告投放平台,营销型网站建设价格贵吗,56做视频网站给定一个不含重复数字的整数数组 nums &#xff0c;返回其 所有可能的全排列 。可以 按任意顺序 返回答案。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,3] 输出&#xff1a;[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 1 < nums.length < 6 -10 < nu…

给定一个不含重复数字的整数数组 nums ,返回其 所有可能的全排列 。可以 按任意顺序 返回答案。

示例 1:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

解法一:直接使用STL:

class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {// next_permutation函数每次产生下一个排列// 下一个排列的含义是按字典顺序下一个更大的排列// 因此需要先对nums进行从小到大排序sort(nums.begin(), nums.end());vector<vector<int>> ans;do {ans.push_back(nums);} while (next_permutation(nums.begin(), nums.end()));return ans;}
};

如果输入数组大小为n,此算法时间复杂度为O(n*n!),空间复杂度为O(1)。next_permutation函数的时间复杂度最多为O(n)。

解法二:回溯法,遍历某个排列的每一个元素,当遍历到下标i时,我们遍历所有可以放到下标i的元素,但有些元素在前面已经用过了,因此我们维护一个visited数组,如果该元素没有用过,才放到下标i:

class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> ans;unordered_set<int> visited;vector<int> current;backtrack(0, current, nums, visited, ans);return ans;}private:void backtrack(int pos, vector<int> current, vector<int> &nums, unordered_set<int> &visited, vector<vector<int>> &ans) {int sz = nums.size();if (pos == sz) {ans.push_back(current);}for (int i = 0; i < sz; ++i) {if (visited.find(nums[i]) != visited.end()) {continue;}visited.insert(nums[i]);current.push_back(nums[i]);backtrack(pos + 1, current, nums, visited, ans);current.pop_back();visited.erase(nums[i]);}}
};

如果输入数组大小为n,此算法时间复杂度为O(n*n!),空间复杂度为O(n)。backtrack函数的调用次数为O(n!),每次调用中,会循环n次。对于空间复杂度,递归深度为n,主要开销是栈空间开销和current、visited数组开销。

解法三:在解法二中,我们使用了visited数组来标记哪些元素已经被全排列过了,我们可以直接修改nums数组,当遍历到下标i时,我们可以令[0,i]的所有元素都是已经全排列过的元素,具体做法是将当前循环中要排列的元素和下标为i的元素交换:

class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> ans;backtrack(0, nums, ans);return ans;}private:void backtrack(int pos, vector<int> &nums, vector<vector<int>> &ans) {int sz = nums.size();if (pos == sz) {ans.push_back(nums);}for (int i = pos; i < sz; ++i) {swap(nums[i], nums[pos]);backtrack(pos + 1, nums, ans);swap(nums[i], nums[pos]);}}
};

如果输入数组大小为n,此算法时间复杂度为O(n*n!),空间复杂度为O(n)。backtrack函数的调用次数为O(n!),每次调用中,会循环n次。对于空间复杂度,递归深度为n,主要开销是栈空间开销。

http://www.dinnco.com/news/37402.html

相关文章:

  • 洛阳青峰网络做网站竞价开户推广
  • 十大黄金软件免费下载seo关键词优化培训
  • 网站月流量是什么意思企业网络推广的方法
  • 滁州市工程建设网站交友网站有哪些
  • 南通电商网站建设免费网站推广软件
  • 做英语教具的网站友情链接平台赚钱吗
  • 哪个网站在线做头像好西安 做网站
  • 山东省建设厅官方网站怎么样免费网页在线客服系统
  • 揭阳网站建设方案外包简述网络营销的特点
  • 自己的网站怎么在百度上面推广哪个公司做网站推广最好
  • 企业融资成本百度搜索关键词排名优化推广
  • 微网站建设招聘最近的国际新闻
  • .name后缀的网站快速seo关键词优化技巧
  • 衡水专业网站建设公司色盲测试图片
  • 分类信息网站如何优化代刷网站推广
  • 自己做个公司网站怎样在百度上做广告推广
  • 做网站起名字网站推广手段
  • 产品推广网站模板网推放单平台
  • 有效的网站建设公司小程序定制开发公司
  • 潞电建设公司官网百度怎么做关键词优化
  • 网站提交入口win7系统优化软件
  • iis 新建网站 要登录国内seo服务商
  • 石家庄西晨网站开发网络建站平台
  • 怎么建设大淘客网站seo快速优化
  • 网站建设及推广方案ppt广州网络推广公司排名
  • 国内公司网站模板百度站长联盟
  • wordpress 个人站关键词点击优化工具
  • 嘉兴网站推广公司网店如何引流与推广
  • 什么网站免费做简历模板深圳正规seo
  • 网站建设的品牌seo排名系统