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

資訊專欄INFORMATION COLUMN

75. Sort Colors

longmon / 1197人閱讀

摘要：題目解題可以參考的這題比較簡(jiǎn)單，就沒(méi)有用書里的解法，的思想就是交換，既然只能，那就一次至少搞定一個(gè)數(shù)啦解法解法只要是遇到或者，就需要采取行動(dòng)

題目：
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, 這題比較簡(jiǎn)單，就沒(méi)有用書里的解法，follow up的思想就是交換，既然只能one pass，那就一次至少搞定一個(gè)數(shù)啦
解法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，就需要采取行動(dòng)
            while (nums[i] == 0 && i >= r || (nums[i] == 2 && i <= b)) {
                if (nums[i] == 0) {
                    swap(nums, i, r++);
                } else {
                    swap(nums, i, b--);
                }
            }
        }
    }

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

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

相關(guān)文章

  • 75. Sort Colors

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

    _ivan 評(píng)論0 收藏0

  • leetcode75. Sort Colors

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

    weizx 評(píng)論0 收藏0

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

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

    techstay 評(píng)論0 收藏0

  • 詳解數(shù)組(Array)引用類型

    摘要：例如，會(huì)刪除數(shù)組中的前兩項(xiàng)。插入的項(xiàng)數(shù)不必與刪除的項(xiàng)數(shù)相等。這兩個(gè)方法都接收兩個(gè)參數(shù)要查找的項(xiàng)和可選的表示查找起點(diǎn)位置的索引。對(duì)數(shù)組中的每一項(xiàng)運(yùn)行給定函數(shù)，返回每次函數(shù)調(diào)用的結(jié)果組成的數(shù)組。 除Object類型外,Array是最常用的類型,Array對(duì)象與其他語(yǔ)言相比有著自己的不同之處,首先同一數(shù)組對(duì)象的不同項(xiàng)可以保存不同類型的數(shù)據(jù),其次數(shù)組對(duì)象的長(zhǎng)短可以動(dòng)態(tài)改變. showImg(...

    afishhhhh 評(píng)論0 收藏0

  • javascript之Array類型-讀書筆記

    摘要：每當(dāng)在末尾添加一項(xiàng)后，其都會(huì)自動(dòng)更新以反應(yīng)這一變化。從而存在兩個(gè)以上不同版本的構(gòu)造函數(shù)。如果數(shù)組中的某一項(xiàng)值是或，那么該值在和方法返回的結(jié)果中以空字符串表示。對(duì)數(shù)組每一項(xiàng)運(yùn)行給定函數(shù)，返回每次函數(shù)調(diào)用的結(jié)果組成的數(shù)組。 Array類型 ECMAscrip與其他多數(shù)語(yǔ)言中數(shù)組的共同點(diǎn)：都是數(shù)據(jù)的有序列表 不同點(diǎn)：數(shù)組的每一項(xiàng)可以保存任何類型的數(shù)據(jù)，數(shù)組的大小是可以動(dòng)態(tài)調(diào)整的，及隨著數(shù)據(jù)...

    kun_jian 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<