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

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

题目

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

 

思路

1. 明说 in-place

2. 先从后面的字符中找到一个较小的, 替代前面的某一个数字, 然后进行一次排序

3. 参考别人的思路. (2) 大体上是对的, 但是细节没有分析. 正确的解法

  a) Find out the first ascending pair from the end of the list.

   Taking the list [2,3,1] as example, we found the 2<3.
   Assuming the index of first element as i, the latter as j. Each time when j=i+1, reset the j to the end of list and --i.
   Turn to step 4 if the pair not found.

  b) if i >= 0, swap the number at indexes i and j.

    After this done, the elements after i is also in descending order.

  c) Reverse the elements after i. And return

  d) If no ascending pair is found, that means the given list is well sorted in the descending order. In this case, just reverse the whole list as required in      this problem.

 

Update

1. 题目有递归性质, "从后面的字符中寻找较小的, 替代前面的某一个数字", 这句话本身就暗示着在找到那个 "较小" 的数字之前, 后面的那些字符必定是有序的. 同时, 寻找的比较过程也保证了, 替换元素后, 后面的字符必然是逆序排列的

 

代码

 

class Solution {public:    void nextPermutation(vector
&num) { int i = num.size()-1; for(; i > 0; i --) { if(num[i] > num[i-1]) { break; } } if(i == 0) { reverse(num.begin(), num.end()); }else{ int lt = i, j; for(j = i; j < num.size(); j++) { if(num[j] <= num[i-1]) { break; } } swap(num[i-1], num[j-1]); sort(num.begin()+i, num.end()); } }};

 

 

 

 

转载地址:http://xrusa.baihongyu.com/

你可能感兴趣的文章
使用erlang 建立一个自动化的灌溉系统(1)准备工作
查看>>
python 调用aiohttp
查看>>
LPAD、RPAD补位函数
查看>>
mysql 案例~ mysql故障恢复
查看>>
UESTC 1307 windy数(数位DP)
查看>>
关于JS面向对象、设计模式、以及继承的问题总结
查看>>
Spring Boot中使用MyBatis注解配置详解
查看>>
MatLab实现FFT与功率谱
查看>>
答《漫话ID》中的疑问:UniqueID和ClientID的来源
查看>>
STL容器--学习笔记
查看>>
使用Word 2010群发邮件
查看>>
【转】Asp.net控件开发学习笔记整理篇 - 服务器控件生命周期
查看>>
Linux下的shell编程(一)BY 四喜三顺
查看>>
hadoop之 心跳时间与冗余快清除
查看>>
执行计划-数据访问方式(全表扫描与4种索引的方式)
查看>>
Shared_ptr循环引用解决(weak_ptr的作用)
查看>>
P1578 奶牛浴场
查看>>
sqlite 数据库错误 The database disk image is malformed database disk image
查看>>
解决MySQL导入中文乱码
查看>>
11、多线程(三) -- 线程池
查看>>