leetcode75. Sort Colors

weizx 發布于2019-08-15 10:41 / 2083人閱讀

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

題目要求

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?

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

思路一：O(2n)

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

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;
            }
        }
    }

思路二：雙指針

如何能在一次遍歷的過程中實現三個數字的排序呢~這就需要使用到雙指針。我們要確保左指針之前的數值全部是0，右指針之后的數值全部是2。這樣他就可以確保左右指針之間的數字為1，從而實現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--);
            }
        }
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 Colors Leetcod LeetCode 75cdn

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/67287.html

75. Sort Colors

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

_ivan 2019-08-16 10:30 評論0 收藏0
[Leetcode] Sort Colors 顏色排序

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

muddyway 2019-08-14 12:32 評論0 收藏0
75. Sort Colors

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

longmon 2019-08-14 14:09 評論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 2019-08-16 13:46 評論0 收藏0
JS基礎篇--JS數組常用方法匯總

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

techstay 2019-08-19 17:18 評論0 收藏0