成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

Next Permutation LC解題記錄

dockerclub / 592人閱讀

摘要：解決思路有一首歌名是下一個天亮，不過和這道題沒什么關(guān)系。根據(jù)這兩個例子猜測，需要兩個輔助的方法，一個是交換，另一個是逆序。所以第一步的思路就是從后往前找，找一對兒符合要求的相鄰數(shù)字。這道題的關(guān)鍵在于，找到規(guī)律，數(shù)學(xué)上的規(guī)律。

題目內(nèi)容

給出一個數(shù)組，重新排列，返回『下一個排列，題目的描述中還給出了幾個例子。

解決思路

有一首歌名是下一個天亮，不過和這道題沒什么關(guān)系。還有一類題是已有一堆數(shù)字要返回所有的排列方式，和這道題也沒什么關(guān)系。按照題目的描述中的例子，比如：
[1,2,3] -> [1,3,2] 觀察了一下，是交換了2和3的位置。
[3,2,1] -> [1,2,3]這個就是整個數(shù)組的逆序排列。
根據(jù)這兩個例子猜測，需要兩個輔助的方法，一個是交換（swap），另一個是逆序（reverse）。
繼續(xù)看，交換的地方應(yīng)該是相鄰兩個數(shù)字后一個比前一個大的情況，而且靠后的優(yōu)先，比如[#$%,1,2,3]返回的也是[#$%,1,3,2]。所以第一步的思路就是從后往前找，找一對兒符合要求的相鄰數(shù)字。如果找到頭都沒找到，那可以直接逆序輸出返回結(jié)果了。
找到這對兒之后，小的數(shù)字肯定要交換到后面的，先設(shè)定這個小數(shù)字的位置是first。然后要交換的數(shù)字是first后面比它大的里面最小的，就是貼著頭皮理發(fā)的感覺。交換過來之后，再把first后面的部分逆序輸出就好了。
這道題的關(guān)鍵在于，找到規(guī)律，數(shù)學(xué)上的規(guī)律。關(guān)鍵的關(guān)鍵在于，找不到規(guī)律就看discussion吧。

code 
public class Solution {
    public void nextPermutation(int[] nums) {
        //排除corner case
        if(nums == null || nums.length < 2) return;
        //找那對兒數(shù)字
        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--;
        }
    }
}
復(fù)雜度分析

這個很顯然是O(n)了，第一遍找一對兒數(shù)字的時候掃了一遍，然后第二次再找nextBig的時候又掃了一遍，最后逆序輸出，掃了好幾次，最后依然是O(n)。

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64963.html

相關(guān)文章

  • [Leetcode]PermutationsI II Next Permutation Permut

    摘要：解題思路這道題是要將排列按字典序排列，然后求出下一個排列，一種辦法是我們先求出所有的排序情況，但是題目規(guī)定不能占有額外空間。每次求出一個數(shù)字后，要及時的把它從中刪除掉。采用來構(gòu)造結(jié)果序列。 PermutationsGiven a collection of distinct numbers, return all possible permutations. For example, ...

    ChristmasBoy 評論0 收藏0

  • LC 267 Palindrome Permutation II

    摘要：判斷一個能否組成一個第一次出現(xiàn)增加一，第二次出現(xiàn)減少一。出現(xiàn)偶數(shù)次的最終對被抵消。出現(xiàn)基數(shù)詞的則會讓加一。類似于，奇數(shù)個的那個單獨考慮，必須放中間。得到各個字符一半數(shù)量的長度數(shù)字的終止條件，利用的對稱性輸出結(jié)果。 Given a string s, return all the palindromic permutations (without duplicates) of it. R...

    lowett 評論0 收藏0

  • Compare Version Numbers LC解題記錄

    摘要：題目內(nèi)容比較不同的版本號，并根據(jù)大小返回，或。并提醒版本意思是第二代的第五次升級，反正不是數(shù)字上的的意思。代碼拆分兩個字符串這里用最大的長度作為循環(huán)范圍因為循環(huán)范圍是最大長度，所以缺的位置補復(fù)雜度分析，和分別是兩個字符串的長度。 題目內(nèi)容 比較不同的版本號，并根據(jù)大小返回-1，1或0。并提醒2.5版本意思是第二代的第五次升級，反正不是數(shù)字上的2.5的意思。 解決思路 直觀的想法是，找到...

    wanglu1209 評論0 收藏0

  • Strobogrammatic Number 系列 LC解題記錄（未完成）

    摘要：所以這題先建立一個對應(yīng)的，然后掃一遍字符串就可以了。復(fù)雜度分析第二題題目內(nèi)容解決思路一看關(guān)鍵詞，通常都是，深搜一遍，挖地三尺，雁過拔毛。復(fù)雜度分析第三題題目內(nèi)容解決思路復(fù)雜度分析 該系列共三道題，Company Tag只有一個Google，那就必須要做了。 第一題題目內(nèi)容 A strobogrammatic number is a number that looks the same ...

    王晗 評論0 收藏0

  • Binary Tree Upside Down LC解題記錄

    摘要：題目內(nèi)容因為這道題被鎖住了，在寫這篇文章時還有天就要過期了，把原題也貼上來。題目要求，樹的結(jié)構(gòu)是每個當(dāng)右邊子節(jié)點的，它肯定有個，就是它的根節(jié)點肯定有個左邊子節(jié)點，也就是說它是二胎。遞歸設(shè)置終止條件，在空節(jié)點或最左邊的葉子處終止。 題目內(nèi)容 Given a binary tree where all the right nodes are either leaf nodes with a...

    Shonim 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<