- 浏览: 183401 次
- 性别:
- 来自: 济南
文章分类
最新评论
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 265Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 267You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 384Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 374Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 497Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 563Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 475Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 664Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 469The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 429Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 575Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 580Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 426All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 898Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 929Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 602Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 672Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 842Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 782You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 704For 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(Visual C++)环境中,我们通常使用C++编程语言来实现这类算法。全排列是指从n个不同元素中取出m(m≤n)个元素,按照...
全排列.
在C++中,标准模板库(STL)提供了next_permutation()函数,可以用来直接生成下一个排列,极大地方便了排列组合的算法实现。 对于时间复杂度,全排列算法至少是O(n!)的复杂度,因为需要生成所有可能的排列组合。...
而穷尽法利用内置的`next_permutation`函数,避免了递归带来的开销,但在某些情况下可能导致效率较低,因为它会生成并检查所有排列。根据具体的应用场景,开发者可以选择合适的方法来实现全排列。
C++标准模板库(STL)提供了一个非常方便的函数`std::next_permutation`,可以直接用来生成序列的下一个字典序排列。此函数接收两个迭代器参数,分别指向序列的起始和终止位置。如果存在下一个字典序排列,则返回`true...
常见得全排列有三种解决方案,for循环穷举,stl摸板函数next_permutation,还有DFS深度优先搜索,当我们遇到带有重复的字符串时应该考虑除去重复的部分。
此外,标签中提到了"C / c++",虽然这里是用C语言实现的,但C++也支持类似的方法,只是语法上有所不同,例如可以使用STL中的`next_permutation`函数来简化代码。 总结起来,字符串全排列是一个经典的计算机科学问题...
在MATLAB中,可以通过定义递归函数,利用“backtracking”或“nextPermutation”等方法实现。具体来说,可以从第一个元素开始,依次尝试与后面的每个元素交换位置,如果满足全排列条件,则记录下来,并继续对下一个...
在这个例子中,`next_permutation`函数会找到当前排列中最后一个按字典序的元素,然后找到比它大的下一个元素并交换它们的位置。如果找不到这样的元素,说明这是该序列的最后一个排列,我们可以通过反转前半部分元素...
使用c++库函数实现全排列,注意next_permutation,使用do{}while()循环
在本文中,我们将深入探讨全排列的两种主要实现方法:递归实现和STL(标准模板库)的`next_permutation()`函数。 **一、递归实现** 递归实现全排列的基本思想是,每次选择一个元素作为当前排列的第一个元素,然后...
本文实例讲述了C++简单实现的全排列算法。分享给大家供大家参考,具体如下: #include stdafx.h #include #include #include void func(const char *str_in) ... }while (std::next_permutation(str.begin(),str
此外,可以使用STL中的`std::next_permutation`函数来简化全排列的实现,但理解递增进位制和递减进位制的原理对于深入学习和理解全排列算法仍然十分必要。 总的来说,使用C++实现全排列算法涉及对递增进位制和递减...
代码功能:生成从1到n的所有排列组合 定义整数 n 并从标准输入读取。 定义一个动态数组(向量)nums,大小为 n...使用 do-while 循环和 next_permutation 函数来生成并打印所有排列组合。每个排列后面打印一个换行符。
在`main`函数中,首先读取并排序数组,然后通过循环调用`next_permutation`生成并打印每个全排列。 枚举法虽然直观,但在处理大规模问题时效率较低,因为其时间复杂度通常较高。因此,理解何时使用枚举法以及如何...
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]...