- 浏览: 172706 次
- 性别:
- 来自: 济南
文章分类
最新评论
mplement 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
全排列的问题,根据当前的序列,返回下一个紧邻它的全排列。我们可以从当前序列的最后一个数字开始往前比较,找到一个数字比紧邻它的后面的数字小的位置,记为i, 此时i位置上的数字比
i+1位置上的数字小,如果将这两个数字交换,这个全排列肯定在当前序列的后面,但不能保证是紧邻的,例如当前序列为12365,我们从后面开始找,5小于6 ,如果交换后为12356,这个序列肯定在当前序列的后面;继续往前找,6大于3,交换后的序列为12635,在当前序列的后面,但是不是紧邻当前序列的,我们想要的结果为12536。因此我们找到第一个f(i) < f(i + 1)的位置后,还要把f(i)元素与f(i + 1)后面的元素进行比较,找到第一个比f(i)大的元素f(x), 然后将f(x)与f(i)交换,再将i 后面的元素排列,就得到了结果。代码如下:
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
全排列的问题,根据当前的序列,返回下一个紧邻它的全排列。我们可以从当前序列的最后一个数字开始往前比较,找到一个数字比紧邻它的后面的数字小的位置,记为i, 此时i位置上的数字比
i+1位置上的数字小,如果将这两个数字交换,这个全排列肯定在当前序列的后面,但不能保证是紧邻的,例如当前序列为12365,我们从后面开始找,5小于6 ,如果交换后为12356,这个序列肯定在当前序列的后面;继续往前找,6大于3,交换后的序列为12635,在当前序列的后面,但是不是紧邻当前序列的,我们想要的结果为12536。因此我们找到第一个f(i) < f(i + 1)的位置后,还要把f(i)元素与f(i + 1)后面的元素进行比较,找到第一个比f(i)大的元素f(x), 然后将f(x)与f(i)交换,再将i 后面的元素排列,就得到了结果。代码如下:
public class Solution { public void nextPermutation(int[] nums) { if(nums == null || nums.length == 0) return; for(int i = nums.length - 1; i > 0; i--) { if(nums[i] > nums[i - 1]) { int j = nums.length - 1; while(j > i - 1 && nums[j] <= nums[i - 1]) j --; int tem = nums[i - 1]; nums[i - 1] = nums[j]; nums[j] = tem; java.util.Arrays.sort(nums, i, nums.length); return; } } //当前序列为321这种情况时 reverse(nums); } public void reverse(int[] nums) { int l = 0; int r = nums.length - 1; while(l < r) { int tem = nums[l]; nums[l++]= nums[r]; nums[r--] = tem; } } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 223Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 222You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 338Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 329Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 447Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 426Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 424The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 382Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 513Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 526Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 366All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 877Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 550Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 595Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 760Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 728You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 625For a undirected graph with tre ...
相关推荐
DFS搜索案例——寻找全排列。 深度优先遍历图的方法是,从图中某顶点v出发: (1)访问顶点v; (2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问; (3)若此时图...
4 }while(next_permutation(a,a+n)); 下面的代码可产生1~n的全排列 #include #include using namespace std; int main(){ int n; while(scanf("%d",&n)&&n){ int a[1000]; for(int i=0;i<n;i++){ scanf(...
全排列 VC 源代码 全排列 VC 源代码 全排列 VC 源代码
全排列.
全排列算法有两个比较常见的实现:递归排列和字典序排列。 (1)递归实现 从集合中依次选出每一个元素,作为排列的第一个...这种方式实现得到的所有排列是按字典序有序的,这也是C++ STL算法next_permutation的思想
常见得全排列有三种解决方案,for循环穷举,stl摸板函数next_permutation,还有DFS深度优先搜索,当我们遇到带有重复的字符串时应该考虑除去重复的部分。
使用c++库函数实现全排列,注意next_permutation,使用do{}while()循环
本文实例讲述了C++简单实现的全排列算法。分享给大家供大家参考,具体如下: #include stdafx.h #include #include #include void func(const char *str_in) ... }while (std::next_permutation(str.begin(),str
1.next_permutation(a+1,a+1+n) a[1-n]全排列 2.reverse(a+1,a+1+n) 将a[1-n]的数翻转过来 3.*max_element(a+1,a+1+n) 找出a[1-n]数字最大值(*是因为这个函数是一个指针) 4.*min_element(a+1,a+1+n) 找出a[1-n]...
leetcode中国 LeetCode | LuoGu 题型记录 P1980 计数问题 (数位dp, 朴素算法) P1047 校门外的树 (线段树, ...全排列问题(next_permutation, dfs(最主要需要记住,置位后需要清0(f[i]=0))) P3392 涂国旗(组合) P23