国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

LeetCode 75. Sort Colors

2019-11-11 05:15:57
字體:
來源:轉載
供稿:網友

描述 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.

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?

分析 由于 0, 1, 2 非常緊湊,首先想到計數排序 (counting sort),但需要掃描兩遍,不符合題目要求。 由于只有三種顏色,可以設置兩個 index,一個是 red 的 index,一個是 blue 的 index,兩邊往中 間走。時間復雜度 O(n),空間復雜度 O(1)。 第 3 種思路,利用快速排序里 partition 的思想,第一次將數組按 0 分割,第二次按 1 分割,排 序完畢,可以推廣到 n 種顏色,每種顏色有重復元素的情況。

代碼

class Solution {public: void sortColors(vector<int>& nums) { const int n = nums.size(); int red = 0; int blue = n - 1; for (size_t i = 0; i < blue + 1;) { if (nums[i] == 0) swap(nums[i++], nums[red++]); else if (nums[i] == 2) swap(nums[i], nums[blue--]); else i++; } }};
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 衡阳县| 社会| 禹州市| 宁陵县| 杭锦旗| 微山县| 东宁县| 慈溪市| 神池县| 巴彦县| 尉氏县| 仙桃市| 沾益县| 云龙县| 千阳县| 兴仁县| 德保县| 丹阳市| 三穗县| 天津市| 麻江县| 绥化市| 通山县| 灌阳县| 德江县| 阿克| 茌平县| 大足县| 海兴县| 大厂| 屯门区| 延安市| 枞阳县| 巴里| 兴和县| 华亭县| 衢州市| 东兴市| 宾阳县| 合水县| 门头沟区|