75. Sort Colors

_ivan 發(fā)布于2019-08-16 10:30 / 3407人閱讀

摘要：題目鏈接這題是給數(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)數(shù)組即可。

// count appears time of each number
        int[] count = new int[3];
        for(int num : nums) count[num]++;
        int k = 0;
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < count[i]; j++) {
                nums[k++] = i;
            }
        }

還有一種方法是用three way partition，參考算法這本書上的講解和程序：
http://algs4.cs.princeton.edu...
http://algs4.cs.princeton.edu...

public class Solution {
    public void sortColors(int[] nums) {
        int i = 0, j = nums.length - 1;
        int pivot = 1;
        int k = 0;
        while(k <= j) {
            if(nums[k] < pivot) swap(nums, i++, k++);
            else if(nums[k] > pivot) swap(nums, k, j--);
            else k++;
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

云服務(wù)器 GPU云服務(wù)器 Colors 75cdn iis75優(yōu)化 75招學會數(shù)據(jù)分析

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

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

相關(guān)文章

leetcode75. Sort Colors

摘要：將數(shù)組中的數(shù)字排序，盡量實現(xiàn)時間復雜度。然后在第二次遍歷數(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 obj...

weizx 2019-08-15 10:41 評論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 2019-08-14 14:09 評論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 2019-08-19 17:18 評論0 收藏0
詳解數(shù)組(Array)引用類型

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

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

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

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