Next Permutation LC解题记录

dockerclub 发布于2019-08-14 14:21 / 465人阅读

摘要：解决思路有一首歌名是下一个天亮，不过和这道题没什么关系。根据这两个例子猜测，需要两个辅助的方法，一个是交换，另一个是逆序。所以第一步的思路就是从后往前找，找一对儿符合要求的相邻数字。这道题的关键在于，找到规律，数学上的规律。

题目内容

给出一个数组，重新排列，返回『下一个排列，题目的描述中还给出了几个例子。

解决思路

有一首歌名是下一个天亮，不过和这道题没什么关系。还有一类题是已有一堆数字要返回所有的排列方式，和这道题也没什么关系。按照题目的描述中的例子，比如：
[1,2,3] -> [1,3,2] 观察了一下，是交换了2和3的位置。
[3,2,1] -> [1,2,3]这个就是整个数组的逆序排列。
根据这两个例子猜测，需要两个辅助的方法，一个是交换（swap），另一个是逆序（reverse）。
继续看，交换的地方应该是相邻两个数字后一个比前一个大的情况，而且靠后的优先，比如[#$%,1,2,3]返回的也是[#$%,1,3,2]。所以第一步的思路就是从后往前找，找一对儿符合要求的相邻数字。如果找到头都没找到，那可以直接逆序输出返回结果了。
找到这对儿之后，小的数字肯定要交换到后面的，先设定这个小数字的位置是first。然后要交换的数字是first后面比它大的里面最小的，就是贴着头皮理发的感觉。交换过来之后，再把first后面的部分逆序输出就好了。
这道题的关键在于，找到规律，数学上的规律。关键的关键在于，找不到规律就看discussion吧。

code

public class Solution {
    public void nextPermutation(int[] nums) {
        //排除corner case
        if(nums == null || nums.length < 2) return;
        //找那对儿数字
        int right = nums.length-1;
        while(right > 0){
            if(nums[right-1] < nums[right]){
                break;
            }
            right--;
        }
        //没找着符合要求的情况，直接reverse。
        if(right == 0){
            reverse(nums, 0, nums.length-1);
            return;
        }
        
        int first = right-1;
        int nextBig = right;
        while(right < nums.length){
            //要大，还不能太大。
            if(nums[right] <= nums[nextBig] && nums[right] > nums[first]){
                nextBig = right;
            }
            right++;
        }
        swap(nums, first, nextBig);
        reverse(nums, first+1, nums.length-1);
    }
    
    private void swap(int[] nums, int first, int second){
        int temp = nums[first];
        nums[first] = nums[second];
        nums[second] = temp;
        return;
    }
    private void reverse(int[] nums,int start, int end){
        while(start < end){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

复杂度分析

这个很显然是O(n)了，第一遍找一对儿数字的时候扫了一遍，然后第二次再找nextBig的时候又扫了一遍，最后逆序输出，扫了好几次，最后依然是O(n)。

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64963.html

[Leetcode]PermutationsI II Next Permutation Permut

摘要：解题思路这道题是要将排列按字典序排列，然后求出下一个排列，一种办法是我们先求出所有的排序情况，但是题目规定不能占有额外空间。每次求出一个数字后，要及时的把它从中删除掉。采用来构造结果序列。 PermutationsGiven a collection of distinct numbers, return all possible permutations. For example, ...

ChristmasBoy 2019-08-16 10:26 评论0 收藏0
LC 267 Palindrome Permutation II

摘要：判断一个能否组成一个第一次出现增加一，第二次出现减少一。出现偶数次的最终对被抵消。出现基数词的则会让加一。类似于，奇数个的那个单独考虑，必须放中间。得到各个字符一半数量的长度数字的终止条件，利用的对称性输出结果。 Given a string s, return all the palindromic permutations (without duplicates) of it. R...

lowett 2019-08-14 17:58 评论0 收藏0
Compare Version Numbers LC解题记录

摘要：题目内容比较不同的版本号，并根据大小返回，或。并提醒版本意思是第二代的第五次升级，反正不是数字上的的意思。代码拆分两个字符串这里用最大的长度作为循环范围因为循环范围是最大长度，所以缺的位置补复杂度分析，和分别是两个字符串的长度。题目内容比较不同的版本号，并根据大小返回-1，1或0。并提醒2.5版本意思是第二代的第五次升级，反正不是数字上的2.5的意思。解决思路直观的想法是，找到...

wanglu1209 2019-08-19 10:45 评论0 收藏0
Strobogrammatic Number 系列 LC解题记录（未完成）

摘要：所以这题先建立一个对应的，然后扫一遍字符串就可以了。复杂度分析第二题题目内容解决思路一看关键词，通常都是，深搜一遍，挖地三尺，雁过拔毛。复杂度分析第三题题目内容解决思路复杂度分析该系列共三道题，Company Tag只有一个Google，那就必须要做了。第一题题目内容 A strobogrammatic number is a number that looks the same ...

王晗 2019-08-14 14:23 评论0 收藏0
Binary Tree Upside Down LC解题记录

摘要：题目内容因为这道题被锁住了，在写这篇文章时还有天就要过期了，把原题也贴上来。题目要求，树的结构是每个当右边子节点的，它肯定有个，就是它的根节点肯定有个左边子节点，也就是说它是二胎。递归设置终止条件，在空节点或最左边的叶子处终止。题目内容 Given a binary tree where all the right nodes are either leaf nodes with a...

Shonim 2019-08-14 14:21 评论0 收藏0