博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
leetcode31
阅读量:6243 次
发布时间:2019-06-22

本文共 1981 字,大约阅读时间需要 6 分钟。

class Solution {public:    void nextPermutation(vector
&nums) { int len = nums.size(); int k = -1, l = 0, i = 0;//注意三个变量的初始化值 for (i = len - 2/*即倒数第二个元素(逆序遍历)*/;i >= 0;--i) if (nums[i + 1] > nums[i]) { k = i; break;//因为是逆序,故此时得到的k一定是最大的 } if (k == -1) { reverse(nums.begin(), nums.end());//此时代表原数组为逆序排列,故直接反转 return; } //接下来找i for (i = len - 1;i >= 0;--i) { if (nums[i] > nums[k]) { l = i; break; } } //二者交换 swap(nums[k], nums[l]); //再反转k之后的元素(不包括nums[k]) reverse(nums.begin() + k + 1, nums.end()); }};

补充一个非常复杂,不美观的版本,使用python实现,也可以AC,能写出来我也挺佩服自己的。

这个版本的主要思想就是从后向前找,记录已查找范围的最大值,当查找到一个值a比已查找区域的最大值maxnum要小的时候,就可以进行换位操作了。

但是要确定一个在已查找区域中比a值大的最小的那个值来进行交换。所以这段代码写的不太美观,如果有高级一点的api可能更美观一些吧。

1 class Solution:     2     def nextPermutation(self, nums: 'List[int]') -> 'None': 3         for i in range(len(nums)-1,-1,-1): 4             basenum = nums[i] 5             maxnum = basenum 6             for j in range(i-1,-1,-1): 7                 curnum = nums[j] 8                 maxnum = max(maxnum,curnum) 9                 if curnum < maxnum:10                     for x in sorted(nums[j:]):11                         if x > curnum:12                             z = j - 113                             for y in nums[j:]:14                                 z += 115                                 if x == y:16                                     slices1 = nums[j:z]17                                     slices2 = nums[z+1:]18                                     slices1.extend(slices2)19                                     nums[j] = nums[z]20                                     nums[j+1:]=sorted(slices1)21                                     return22 23                     24         nums.sort()

 

转载于:https://www.cnblogs.com/asenyang/p/9837080.html

你可能感兴趣的文章
【maven】 pom.xml详解
查看>>
LINQ中的OrderBy实现多字段升序、降序排序实现
查看>>
idea14导入eclipse项目并部署运行完整步骤
查看>>
杀死O2O的三大杀手?!
查看>>
<Android 应用 之路> 百度地图API使用(1)
查看>>
Java的结构之美【1】——构造对象
查看>>
Android双向滑动菜单完全解析,教你如何一分钟实现双向滑动特效
查看>>
「译」JavaScript 的怪癖 2:两个「空值」:undefined 和 null
查看>>
第一章 计算机系统漫游
查看>>
Android Activity 生命周期再验证
查看>>
shift-and 算法初体验
查看>>
sweetalert api中文开发文档和手册
查看>>
网络视频监控
查看>>
winter 2018 02 01 关于模运算的一道题
查看>>
stack的简单用法总结
查看>>
SpringCloud学习成长之路 五 路由器网关
查看>>
SpringMVC
查看>>
Ubuntu 10.04 源码编译安装bochs 2.4.5
查看>>
iOS Full Sensor Video Output
查看>>
odoo开发笔记 -- 权限机制
查看>>