`
huntfor
  • 浏览: 201550 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetcode]Next Permutation

 
阅读更多

怎么说呢,这篇博文的算法还是很不错的,新博文采用的还是这篇博文的就算法,只不过代码更简洁,可能读可能更好一点,有兴趣请移步,新博文地址:[leetcode]Next Permutation

Next Permutation

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

 给你一个数字组成的字符串,这组数字可以排列成大概n!个数字(当有重复数字的时候,排列数< n!)结果要求你返回排列中原字符串的后驱数字。

例如123可以组成123,132,213,231,312,321,其中132是123的后驱,同理213是132的后驱,当321达到最大时,则返回最小的排列情况123,最为其后驱。

这道题比较折腾,做了很长时间。

我的算法首先必须从后往前遍历。原因很明显,请往下看:

1. 从后往前遍历,找到临界点

1.1 如果发现某个位置,前面的数字变小了。比如132中,1比3小,则1就是临界点。

1. 2 如果数字越来越大,比如321。2比1,3比2大,则这个数是最大的。这是显然的。标记之。

 

2.从1后面的3开始往后遍历,找到比1大的最小的数字,本例中是2。然后将2与1交换。这时数字变成了231

3.对2后面的所有数字做排序,即对31做排序,得到13,最终结果是213。

这下大家就很明显的看出来为什么必须从后往前遍历。

代码如下:

    public void nextPermutation(int[] num) {
        if(num == null || num.length <= 1){
        	return;
        }
        boolean tag = true;
        for(int i = num.length - 1; i > 0 ; i--){
        	if(num[i] > num[i - 1]){
        		for(int j = i ; j < num.length; j++){
        			if(num[j] > num[i - 1] && (j == num.length - 1 || num[j + 1] <= num[i - 1]  )){
        				int tem = num[j];
        				num[j] = num[i - 1] ;
        				num[i - 1] = tem;
        				break;
        			}
        		}
        		int[] copy = Arrays.copyOfRange(num, i ,num.length);
        		Arrays.sort(copy);
        		for(int j = i; j < num.length; num[j] = copy[j - i],j++);
        		tag = false;//标记找到了临界点
        		break;
        	}
        }    
        if(tag){//如果没有找到临界点,则该排列数是最大的,变为最小的即可
        	for(int i = 0; i < num.length / 2; i++){
        		int temp = num[i];
        		num[i] = num[num.length - 1 - i];
        		num[num.length - 1 - i] = temp;
        	}
        }
    }

 

 

 

分享到:
评论

相关推荐

    java-leetcode题解之Next Permutation.java

    java java_leetcode题解之Next Permutation.java

    31.Next Permutation 下一个排列【LeetCode单题讲解系列】

    31.Next_Permutation_下一个排列【LeetCode单题讲解系列】

    js-leetcode题解之31-next-permutation.js

    js js_leetcode题解之31-next-permutation.js

    LeetCode最全代码

    # [LeetCode](https://leetcode.com/problemset/algorithms/) !... Up to date (2016-12-18), there are `447` Algorithms / `13` ...31 | [Next Permutation](https://leetcode.com/problems/next-permutation/)| ...

    戳气球leetcode-leetcode:leetcode

    leetcode category other hot keywords:Palindrome(mic), Subsequence Array 螺旋矩阵Spiral Matrix 顺时针打印矩阵 Next Permutation Product of Array Except Self 189.rotate-array 283.move-zero Range Sum ...

    Leetcode答案(c++版)

    **1.28 Next Permutation (31)** - **问题描述**:实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 - **解题思路**: - 从后向前找到第一个升序对 (nums[i-1], nums[i])。...

    Leetcode题目+解析+思路+答案.pdf

    - **Populating Next Right Pointers in Each Node**:连接二叉树每个节点的下一个右侧节点。 - **Convert Sorted List/Array to Binary Search Tree**:将有序列表或数组转换为二叉搜索树。 - **Path Sum II**:...

    leetcode-常见考题2.pdf

    - 在 NextPermutation 题目中,需要使用递归或迭代来寻找给定数列的下一个全排列。 这些知识点构成了算法面试的主要考察内容,应聘者如果能熟练掌握这些知识,将有助于在IT行业的面试中获得更好的表现。

    leetcode最大连通域-leetcode:leetcode

    next_permutation.py - 将数字重新排列为按字典顺序排列的下一个更大的数字排列 permutations2.py - 返回所有可能的唯一排列 3sum_2.py - 查找数组中所有唯一的三元组,其总和为零。 3sum.py - 查找数组中所有唯一的...

    最低加油次数leetcode-Leetcode:力码

    最低加油次数 ...Next_permutation Stack, trick trick TOP 类似斐波拉契,一层层处理 字符串处理 TOP 完全背包 dfs Trick TOP next_permutation dfs or stl next_permutation dfs or stl TOP 排序后的字符串作

    leetcode1004-leetcode:leetcode

    Permutation (M) * -&gt; index 주의, 부등호 하나 틀림 33. Search in Rotated Sorted Array (M) * -&gt; 부등호 주의, 부등호 하나 틀림 34. Find First and Last Position of Element in Sorted Array (M) 35. Search ...

    leetcode2sumc-Leetcode_imp_C:Leetcode在C上的实现

    leetcode_0031_next_permutation.c leetcode_0033_search_rotate.c : binary search, offer11 81 leetcode_0034_first_last_pos.c : binary search leetcode_0035_search_inseart.c : binary search leetcode...

    leetcode答案-exercise-book:算法练习记录

    Permutation 解决方法:掌握排列组合的字典序规律,即可。这个规律找不到,我最后还是直接看答案的。 LeetCode: 581. Shortest Unsorted Continuous Subarray 解决方法:无序列中最大最小值 2018-08-17 19:47 ...

    lrucacheleetcode-LeetCode:这个库用于总结leetcode中遇到的习题,期望按照数据结构和常用方法分成2类,进行总结,

    lru cache leetcode LeetCode 这个库用于总结leetcode中遇到的习题 常用数据结构习题总结 1.线性表 解决进度 ...Next Permutation 公式 13 Permutation Sequence 公式 14 Valid Sudoku 15 Trapping Rain W

    C语言基础-C语言编程基础之Leetcode编程题解之第31题下一个排列.zip

    对于这道题,常见的解法有两种:一是使用STL库中的`next_permutation`函数,二是自定义算法实现。在C语言中,由于没有内置的`next_permutation`函数,我们需要自己编写算法。一种常见的自定义方法是先找到序列中最后...

    leetcode装最多水-Leetcode:解决了leetcode问题

    Permutation 算法也可用于迭代地查找数组的排列。 也可用于迭代查找数组的排列。 13 . 14 . 15 . 16 . 17 . Algorithm to find kth largest element from an unsorted array in linear time. (1) If the number of ...

    leetcode最大蓄水量-leetcode_note_book:leetcode题目分类及刷题总结

    NextPermutation 下一排序 完成 DFS 题目 说明 状态 NumIslands 岛屿数量 完成 DivideAndConquer 题目 说明 状态 MaxSubArray 最大子序和 完成 Back Tracing 题目 说明 状态 GenerateParenthesis 括号生成 完成 ...

    LeetCode:LeetCode练习

    STL算法常用函数:分隔组合:next_permutation()是检索当前范围内的划分,并重新排序为下一个替换,leetcode 556下一个元素元素III prev_permutation()是替换指定范围内的序列重新排列它重新排序为上一个序列。...

    leetcode-cpp刷题

    - **2.1.12 Next Permutation** - 寻找下一个更大的排列。 - 实现思路:从右向左扫描数组,找到第一个下降位置,然后交换该位置及其右侧的最大值,最后将右侧部分反转。 - **2.1.13 Permutation Sequence** - ...

Global site tag (gtag.js) - Google Analytics