75. Sort Colors

longmon 發布于2019-08-14 14:09 / 1194人閱讀

摘要：題目解題可以參考的這題比較簡單，就沒有用書里的解法，的思想就是交換，既然只能，那就一次至少搞定一個數啦解法解法只要是遇到或者，就需要采取行動

題目：
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.

click to show follow up.

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?

解題：
可以參考EPI的14.8, 這題比較簡單，就沒有用書里的解法，follow up的思想就是交換，既然只能one pass，那就一次至少搞定一個數啦
解法1:

public void Color(int[] nums, int color, int start, int len) {
        for (int i = start; i < start + len; i++) {
            nums[i] = color;
        }
    }
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) return;
        
        Map map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 1);
            } else {
                map.put(nums[i], map.get(nums[i]) + 1);
            }
        }
        
        int r = map.get(0) != null ? map.get(0) : 0;
        int w = map.get(1) != null ? map.get(1) : 0;
        int b = map.get(2) != null ? map.get(2) : 0;
        
        Color(nums, 0, 0, r);
        Color(nums, 1, r, w);
        Color(nums, 2, r + w, b);
    }

Follow up解法：

public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) return;
        
        int r = 0, b = nums.length - 1;
        for (int i = 0; i < nums.length; i++) {
        //只要是遇到0或者2，就需要采取行動
            while (nums[i] == 0 && i >= r || (nums[i] == 2 && i <= b)) {
                if (nums[i] == 0) {
                    swap(nums, i, r++);
                } else {
                    swap(nums, i, b--);
                }
            }
        }
    }

云服務器 GPU云服務器 Colors 75cdn iis75優化 75招學會數據分析

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

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

75. Sort Colors

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

_ivan 2019-08-16 10:30 評論0 收藏0
leetcode75. Sort Colors

摘要：將數組中的數字排序，盡量實現時間復雜度。然后在第二次遍歷數組的過程中，將相應次數的，，依序填入數組中。我們要確保左指針之前的數值全部是，右指針之后的數值全部是。這樣他就可以確保左右指針之間的數字為，從而實現，，的排序。題目要求 Given an array with n objects colored red, white or blue, sort them so that obj...

weizx 2019-08-15 10:41 評論0 收藏0
JS基礎篇--JS數組常用方法匯總

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

techstay 2019-08-19 17:18 評論0 收藏0
詳解數組(Array)引用類型

摘要：例如，會刪除數組中的前兩項。插入的項數不必與刪除的項數相等。這兩個方法都接收兩個參數要查找的項和可選的表示查找起點位置的索引。對數組中的每一項運行給定函數，返回每次函數調用的結果組成的數組。除Object類型外,Array是最常用的類型,Array對象與其他語言相比有著自己的不同之處,首先同一數組對象的不同項可以保存不同類型的數據,其次數組對象的長短可以動態改變. showImg(...

afishhhhh 2019-08-21 10:48 評論0 收藏0
javascript之Array類型-讀書筆記

摘要：每當在末尾添加一項后，其都會自動更新以反應這一變化。從而存在兩個以上不同版本的構造函數。如果數組中的某一項值是或，那么該值在和方法返回的結果中以空字符串表示。對數組每一項運行給定函數，返回每次函數調用的結果組成的數組。 Array類型 ECMAscrip與其他多數語言中數組的共同點：都是數據的有序列表不同點：數組的每一項可以保存任何類型的數據，數組的大小是可以動態調整的，及隨著數據...

kun_jian 2019-08-20 15:49 評論0 收藏0