75. Sort Colors

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

摘要：題目鏈接這題是給數(shù)組排序，數(shù)組里面只有個(gè)變量。一個(gè)方法是用類似，個(gè)桶，統(tǒng)計(jì)三個(gè)變量出現(xiàn)的個(gè)數(shù)，然后重構(gòu)數(shù)組即可。還有一種方法是用，參考算法這本書(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)數(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，參考算法這本書(shū)上的講解和程序：
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招學(xué)會(huì)數(shù)據(jù)分析

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/69901.html

相關(guān)文章

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 2019-08-15 10:41 評(píng)論0 收藏0
75. Sort Colors

摘要：題目解題可以參考的這題比較簡(jiǎn)單，就沒(méi)有用書(shū)里的解法，的思想就是交換，既然只能，那就一次至少搞定一個(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...

longmon 2019-08-14 14:09 評(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 2019-08-19 17:18 評(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 2019-08-21 10:48 評(píng)論0 收藏0
javascript之Array類型-讀書(shū)筆記

摘要：每當(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 2019-08-20 15:49 評(píng)論0 收藏0