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

注册网站建设购物网站制作免费

注册网站建设,购物网站制作免费,商务互联 网站,现在注册公司流程和费用题意 找到下一个permutation是什么,对于一个数组[1,2,3],下一个排列就是[1, 3, 2] 链接 https://leetcode.com/problems/next-permutation/ 思考 首先任何一个permutation满足一个性质,从某个位置往后一定是降序。…

题意

找到下一个permutation是什么,对于一个数组[1,2,3],下一个排列就是[1, 3, 2]

链接

https://leetcode.com/problems/next-permutation/

思考

首先任何一个permutation满足一个性质,从某个位置往后一定是降序
比如[2,1,4,3]这么一个排列,3和4之间是没有办法交换的了,因为此时已经达到了[2,1]开头的最大值,只能改变1才能够变成一个更大排列。

解法

所以步骤分为三步:
记n为num.size();

  1. 从右往左找,找到位置i,使得nums[i-1] < nums[i]
  2. 此时nums[i-1]是我需要交换的其中元素,我需要在下标区间[i, nums.size()-1]中找到最后一个大于nums[i-1]的元素,和nums[i-1]交换
  3. 把[i,n]这个区间的元素升序排列

解法

//最终优化版本
int i = nums.size() - 1;
while( i > 0 && nums[i-1] >= nums[i]) i--;
if (i == 0) {reverse(nums.begin(), nums.end());return;
}
int l = i;
int r = nums.size() - 1;
int t = nums[i-1];
//二分找到最后一个严格大于nums[i-1]的值
while(l < r) {int mid = l + (r - l)+1 / 2;if(nums[mid] > t) {l = mid;} else {r = mid - 1;}
}
//这里不需要判断答案是否存在,因为while( i > 0 && nums[i-1] >= nums[i]) i--;已经保证了二分一定有值,至少有一个元素是比nums[i-1]要大//交换两个数
swap(nums[i-1], nums[l]);
//把从第i位开始的数字到末尾升序排列
reverse(nums.begin()+i, nums.end());

算法复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)

//没有用二分的版本
class Solution {
public:void nextPermutation(vector<int>& nums) {int i = nums.size()-2;for(; i >= 0; i--) {if(nums[i] < nums[i+1])break;}if (i == -1) {return reverse(nums.begin(),nums.end());}int j = nums.size()-1;for(; j >= 0; j--) {if(nums[j] > nums[i]) {swap(nums[j], nums[i]);break;}}return reverse(nums.begin()+i+1, nums.end());}
};

算法复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)

http://www.yayakq.cn/news/124684/

相关文章:

  • 友情链接对网站的作用哈尔滨网站建设方案开发
  • 网站建设行业分析报告网页游戏制作引擎
  • 礼品网站制作模板网站和定制网站的区别
  • 安阳哪里有做网站的wordpress在线制作
  • 重庆旅游seo整站优化dede小视频网站源码
  • 买完域名后怎么做网站自助商城
  • 智能建站公司网站流量怎么挣钱
  • 做网站不用tomcat行吗做公众号文章的网站
  • wordpress网站vip可看线上推广员是干什么的
  • 苏州网站建设哪里好开发网站的申请怎么写
  • seo网站推广优化就找微源优化wordpress微信登录插件下载
  • 网站建设推广软件华润置地建设事业部网站
  • 浙江网站建设外贸凯里建设局网站
  • 推荐一个免费的网站向google提交网站
  • 推荐的网站wordpress 主题黑
  • 做门户网站要多少钱番禺网站制作多少钱
  • 上海微信网站公司哪家好扬州网站建设myvodo
  • 合肥网站快速优化排名菲律宾 网站开发公司
  • 网站开发建设推荐网页制作软件dw与python软件对比
  • 关于做无机化学实验的网站宝应网站
  • 龙岩网站设计制作wordpress cdn无作用
  • 高端品牌网站开发iis 5 如何添加网站
  • 微网站的特点一个小程序一年的费用是多少
  • 网站标题采集建设部职称证书查询官方网站
  • 做网站建设销售辛苦吗密云新闻 今天 最新
  • 天津企业网站开发wordpress payjs
  • 查询公司水利平台网站在菲做平台网站
  • 手机网站建设代理商佛山新网站建设方案
  • 免费建网站的平台手机网站与pc网站同步
  • 有必要自建网站做导购吗WordPress对接易支付