`

Next Permutation 全排列

阅读更多
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 后面的元素排列,就得到了结果。代码如下:
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;
        }
    }
}
0
1
分享到:
评论

相关推荐

    DFS搜索 全排列 next_permutation.cpp

    DFS搜索案例——寻找全排列。 深度优先遍历图的方法是,从图中某顶点v出发: (1)访问顶点v; (2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问; (3)若此时图...

    详谈全排列next_permutation() 函数的用法(推荐)

    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&lt;n;i++){ scanf(...

    全排列VC源代码,仅供参考

    全排列是一种经典的算法问题,广泛应用于计算机科学,特别是在数据结构和算法的学习中。在VC(Visual C++)环境中,我们通常使用C++编程语言来实现这类算法。全排列是指从n个不同元素中取出m(m≤n)个元素,按照...

    next_permutation.cpp

    全排列.

    全排列算法解析(完整版)

    在C++中,标准模板库(STL)提供了next_permutation()函数,可以用来直接生成下一个排列,极大地方便了排列组合的算法实现。 对于时间复杂度,全排列算法至少是O(n!)的复杂度,因为需要生成所有可能的排列组合。...

    全排列C++实现

    而穷尽法利用内置的`next_permutation`函数,避免了递归带来的开销,但在某些情况下可能导致效率较低,因为它会生成并检查所有排列。根据具体的应用场景,开发者可以选择合适的方法来实现全排列。

    全排列算法解析(完整版)

    C++标准模板库(STL)提供了一个非常方便的函数`std::next_permutation`,可以直接用来生成序列的下一个字典序排列。此函数接收两个迭代器参数,分别指向序列的起始和终止位置。如果存在下一个字典序排列,则返回`true...

    带油重复字符串全排列递归解法

    常见得全排列有三种解决方案,for循环穷举,stl摸板函数next_permutation,还有DFS深度优先搜索,当我们遇到带有重复的字符串时应该考虑除去重复的部分。

    求字符串的全排列

    此外,标签中提到了"C / c++",虽然这里是用C语言实现的,但C++也支持类似的方法,只是语法上有所不同,例如可以使用STL中的`next_permutation`函数来简化代码。 总结起来,字符串全排列是一个经典的计算机科学问题...

    生成全排列矩阵.zip

    在MATLAB中,可以通过定义递归函数,利用“backtracking”或“nextPermutation”等方法实现。具体来说,可以从第一个元素开始,依次尝试与后面的每个元素交换位置,如果满足全排列条件,则记录下来,并继续对下一个...

    全排列算法

    在这个例子中,`next_permutation`函数会找到当前排列中最后一个按字典序的元素,然后找到比它大的下一个元素并交换它们的位置。如果找不到这样的元素,说明这是该序列的最后一个排列,我们可以通过反转前半部分元素...

    stl实现全排列

    使用c++库函数实现全排列,注意next_permutation,使用do{}while()循环

    深入全排列算法及其实现方法

    在本文中,我们将深入探讨全排列的两种主要实现方法:递归实现和STL(标准模板库)的`next_permutation()`函数。 **一、递归实现** 递归实现全排列的基本思想是,每次选择一个元素作为当前排列的第一个元素,然后...

    C++简单实现的全排列算法示例

    本文实例讲述了C++简单实现的全排列算法。分享给大家供大家参考,具体如下: #include stdafx.h #include #include #include void func(const char *str_in) ... }while (std::next_permutation(str.begin(),str

    使用C++实现全排列算法的方法详解

    此外,可以使用STL中的`std::next_permutation`函数来简化全排列的实现,但理解递增进位制和递减进位制的原理对于深入学习和理解全排列算法仍然十分必要。 总的来说,使用C++实现全排列算法涉及对递增进位制和递减...

    #P0015. 全排列 超级简单

    代码功能:生成从1到n的所有排列组合 定义整数 n 并从标准输入读取。 定义一个动态数组(向量)nums,大小为 n...使用 do-while 循环和 next_permutation 函数来生成并打印所有排列组合。每个排列后面打印一个换行符。

    南邮ACM算法与数据结构设计第5讲PPT教案学习.pptx

    在`main`函数中,首先读取并排序数组,然后通过循环调用`next_permutation`生成并打印每个全排列。 枚举法虽然直观,但在处理大规模问题时效率较低,因为其时间复杂度通常较高。因此,理解何时使用枚举法以及如何...

    c++中比较好用的“黑科技”

    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]...

Global site tag (gtag.js) - Google Analytics