摘要:當遇到時,將其和序列前面一個數交換,然后將序列的指針向前移。這樣,當我們遍歷到序列開頭時,實際上我們已經排好序了,因為所有都被交換到了前面,所有都被交換到了后面。
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 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.
時間 O(N) 空間 O(1)
思路我們先用兩個指針,一個指向已經排好序的0的序列的后一個點,一個指向已經排好序的2的序列的前一個點。這樣在一開始,兩個指針是指向頭和尾的,因為我們還沒有開始排序。然后我們遍歷數組,當遇到0時,將其和0序列后面一個數交換,然后將0序列的指針向后移。當遇到2時,將其和2序列前面一個數交換,然后將2序列的指針向前移。遇到1時,不做處理。這樣,當我們遍歷到2序列開頭時,實際上我們已經排好序了,因為所有0都被交換到了前面,所有2都被交換到了后面。
代碼public class Solution { public void sortColors(int[] nums) { int left = 0, right = nums.length - 1; int i = 0; while(i <= right){ // 遇到0交換到前面 if(nums[i] == 0){ swap(nums, i, left); left++; // 因為左邊必定有序,所以可以直接i++ i++; // 遇到2交換到后面 } else if(nums[i] == 2){ swap(nums, i, right); right--; } else { // 遇到1跳過 i++; } } } private void swap(int[] nums, int i1, int i2){ int tmp = nums[i1]; nums[i1] = nums[i2]; nums[i2] = tmp; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/64537.html
摘要:將數組中的數字排序,盡量實現時間復雜度。然后在第二次遍歷數組的過程中,將相應次數的,,依序填入數組中。我們要確保左指針之前的數值全部是,右指針之后的數值全部是。這樣他就可以確保左右指針之間的數字為,從而實現,,的排序。 題目要求 Given an array with n objects colored red, white or blue, sort them so that obj...
摘要:題目鏈接這題是給數組排序,數組里面只有個變量。一個方法是用類似,個桶,統計三個變量出現的個數,然后重構數組即可。還有一種方法是用,參考算法這本書上的講解和程序 75. Sort Colors 題目鏈接:https://leetcode.com/problems... 這題是給數組排序,數組里面只有3個變量。一個方法是用類似bucket sort,3個桶,統計三個變量出現的個數,然后重構...
摘要:例如,會刪除數組中的前兩項。插入的項數不必與刪除的項數相等。這兩個方法都接收兩個參數要查找的項和可選的表示查找起點位置的索引。對數組中的每一項運行給定函數,返回每次函數調用的結果組成的數組。 除Object類型外,Array是最常用的類型,Array對象與其他語言相比有著自己的不同之處,首先同一數組對象的不同項可以保存不同類型的數據,其次數組對象的長短可以動態改變. showImg(...
摘要:實現電商網站效果展示下載代碼安裝依賴啟動項目運行環境需求分析登錄頁面商品列表頁網站首頁購物車頁實現結算商品詳情頁可按顏色品牌對商品進行篩選,單擊選中,再次點擊取消根據價格進行升序降序銷量降序排列商品列表顯示圖片名稱銷量顏色單價實時顯示 shopping vue + vue-router + vuex實現電商網站 效果展示 showImg(https://user-gold-cdn.xi...
摘要:實現電商網站效果展示下載代碼安裝依賴啟動項目運行環境需求分析登錄頁面商品列表頁網站首頁購物車頁實現結算商品詳情頁可按顏色品牌對商品進行篩選,單擊選中,再次點擊取消根據價格進行升序降序銷量降序排列商品列表顯示圖片名稱銷量顏色單價實時顯示 shopping vue + vue-router + vuex實現電商網站 效果展示 showImg(https://user-gold-cdn.xi...
閱讀 2368·2021-11-18 10:07
閱讀 2318·2021-09-22 15:59
閱讀 3077·2021-08-23 09:42
閱讀 2276·2019-08-30 15:44
閱讀 1191·2019-08-29 15:06
閱讀 2303·2019-08-29 13:27
閱讀 1210·2019-08-29 13:21
閱讀 1412·2019-08-29 13:13