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

資訊專欄INFORMATION COLUMN

leetcode75. Sort Colors

weizx / 2091人閱讀

摘要：將數(shù)組中的數(shù)字排序，盡量實現(xiàn)時間復(fù)雜度。然后在第二次遍歷數(shù)組的過程中，將相應(yīng)次數(shù)的，，依序填入數(shù)組中。我們要確保左指針之前的數(shù)值全部是，右指針之后的數(shù)值全部是。這樣他就可以確保左右指針之間的數(shù)字為，從而實現(xiàn)，，的排序。

題目要求 
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library"s sort function for this problem.
    
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0"s, 1"s, and 2"s, then overwrite array with total number of 0"s, then 1"s and followed by 2"s.

Could you come up with an one-pass algorithm using only constant space?

假設(shè)一個數(shù)組中存在3個數(shù)字0，1，2。將數(shù)組中的數(shù)字排序，盡量實現(xiàn)O(n)時間復(fù)雜度。

思路一：O(2n)

就如題中所言，先遍歷一遍數(shù)組，分別記錄0，1，2出現(xiàn)的次數(shù)。然后在第二次遍歷數(shù)組的過程中，將相應(yīng)次數(shù)的0，1，2依序填入數(shù)組中。代碼如下：

public void sortColors1(int[] nums) {
        int numOfZero = 0;
        int numOfOne = 0;
        for(int i = 0 ; i < nums.length ; i++){
            if(nums[i]==0){
                numOfZero++;
            }else if(nums[i]==1){
                numOfOne++;
            }
        }
        for(int i = 0 ; i0){
                nums[i] = 0;
                numOfZero--;
            }else if(numOfOne>0){
                nums[i] = 1;
                numOfOne--;
            }else{
                nums[i] = 2;
            }
        }
    }
思路二：雙指針

如何能在一次遍歷的過程中實現(xiàn)三個數(shù)字的排序呢~這就需要使用到雙指針。我們要確保左指針之前的數(shù)值全部是0，右指針之后的數(shù)值全部是2。這樣他就可以確保左右指針之間的數(shù)字為1，從而實現(xiàn)0，1，2的排序。代碼如下：

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
    //保證i前全是0，j后全是2，然后通過交換使得i和j中間確定為1,O(n)
    public void sortColors2(int[] nums) {
        int i = 0;
        int j = nums.length - 1;
        int ptr = 0;
        while (ptr <= j) {
            if (nums[ptr] == 0) {
                swap(nums, i++, ptr++);
            } else if (nums[ptr] == 1) {
                ptr++;
            } else {
                swap(nums, ptr, j--);
            }
        }
    }


想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~

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

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

相關(guān)文章

  • 75. Sort Colors

    摘要：題目鏈接這題是給數(shù)組排序，數(shù)組里面只有個變量。一個方法是用類似，個桶，統(tǒng)計三個變量出現(xiàn)的個數(shù)，然后重構(gòu)數(shù)組即可。還有一種方法是用，參考算法這本書上的講解和程序 75. Sort Colors 題目鏈接：https://leetcode.com/problems... 這題是給數(shù)組排序，數(shù)組里面只有3個變量。一個方法是用類似bucket sort，3個桶，統(tǒng)計三個變量出現(xiàn)的個數(shù)，然后重構(gòu)...

    _ivan 評論0 收藏0

  • [Leetcode] Sort Colors 顏色排序

    摘要：當遇到時，將其和序列前面一個數(shù)交換，然后將序列的指針向前移。這樣，當我們遍歷到序列開頭時，實際上我們已經(jīng)排好序了，因為所有都被交換到了前面，所有都被交換到了后面。 Sort Colors Given an array with n objects colored red, white or blue, sort them so that objects of the same col...

    muddyway 評論0 收藏0

  • 75. Sort Colors

    摘要：題目解題可以參考的這題比較簡單，就沒有用書里的解法，的思想就是交換，既然只能，那就一次至少搞定一個數(shù)啦解法解法只要是遇到或者，就需要采取行動 題目：Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with...

    longmon 評論0 收藏0

  • [LeetCode] 785. Is Graph Bipartite?

    Problem Given an undirected graph, return true if and only if it is bipartite. Recall that a graph is bipartite if we can split its set of nodes into two independent subsets A and B such that every ed...

    godlong_X 評論0 收藏0

  • JS基礎(chǔ)篇--JS數(shù)組常用方法匯總

    摘要：在，下，數(shù)據(jù)有添加成功，但返回值卻是轉(zhuǎn)換方法方法方法用于把數(shù)組中的所有元素放入一個字符串。元素是通過指定的分隔符進行分隔的。而調(diào)用數(shù)組的方法后，其值的順序變成了。返回值如果從中刪除了元素，則返回的是含有被刪除的元素的數(shù)組。 轉(zhuǎn)換方法 所有對象都具有toLocaleString()、toString()、valueOf()方法。其中調(diào)用數(shù)組的toString方法會返回以數(shù)組中的每個值的字...

    techstay 評論0 收藏0

發(fā)表評論

0條評論

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