Sort Colors--LeetCode

向右看齐 2022-08-07 11:44 21阅读 0赞

# 题目： #

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.

思路：类似于快速排序的partition过程，下面的代码是非常纯粹的使用这个思想，事件复杂度为O(n)，其实这里可以将两个循环合并成一个，0是从头开始，2是从尾部开始，但是没有这么做，如果是四个颜色，最好的方式就是首先通过一个循环将其中一个和其余三个分开，然后再一次循环将剩余的三个分开。

#include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    /*
    类似于排序 只不过很多重复的 
    */ 
    void SortColors(vector<int>& vec)
    {
    	int i,j;
    	i = -1;
    	
    	// 先把0排好 
    	for(j=i+1;j<vec.size();j++)
    	{
    		if(vec[j] == 0)
    		{
    			i++;
    			swap(vec[i],vec[j]);
    		} 
    	}
    	 // 再把1 排序好
    	 
    	for(j = i+1;j<vec.size();j++)
    	{
    		if(vec[j] == 1)
    		{
    			i++;
    			swap(vec[i],vec[j]);
    		}
    	}
    } 
    
    int main()
    {
    	vector<int> vec(10);
    	int i;
    	for(i=0;i<vec.size();i++)
    		vec[i] = i%3;
    	SortColors(vec);
    	for(i=0;i<vec.size();i++)
    		cout<<vec[i]<<"  ";
    	cout<<endl;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，21人围观）

还没有评论，来说两句吧...

相关阅读

相关 python的sort与sorted

一、sort 方法 sort 方法是列表的方法，用于在原地对列表进行排序，即直接修改原始列表，不返回新的列表。它可以接受两个可选参数：key 和 reverse。

- 日理万妓/ 2024年03月26日 22:18/ 0 赞/ 21 阅读

相关 Python-sorted与sort，以及模拟内置函数sorted()

sort：修改原列表 sorted：产生一个新的列表 -------------------- >>> help(list.sort) Help on

约定不等于承诺〃/ 2024年02月17日 17:20/ 0 赞/ 20 阅读

相关 Sort

include<iostream> include<vector> include<map> using namespace std;

深碍√TFBOYSˉ_/ 2022年12月16日 13:08/ 0 赞/ 53 阅读

相关 sort和sorted的区别

sort()与sorted()的不同在于，sort是在原位重新排列列表，而sorted()是产生一个新的列表。 sort 是应用在 list 上的方法，sorted 可以对所

痛定思痛。/ 2022年08月31日 09:49/ 0 赞/ 151 阅读

相关 sort

sort Time Limit: 1000ms Memory limit: 32768K 有疑问？点这里^\_^ 题目描述给你n个整数，请按从大到小的顺序输

不念不忘少年蓝@/ 2022年08月10日 05:51/ 0 赞/ 102 阅读

相关 sort()和stable_sort()用法

C ++ sort()与stable\_sort() (2012-04-03 10:07:30) ![sg_trans.gif][]转载▼ <table styl

秒速五厘米/ 2022年08月04日 10:49/ 0 赞/ 205 阅读

相关 sort() , sorted() 与argsort()

sort() 是可变对象的（字典、列表）方法，无参数、无返回值，因为它可以改变对象，因此无需返回值。sort()方法对于不可变对象（如元组、字符串）是不能调用的。 ![这里

本是古典何须时尚/ 2022年07月26日 05:28/ 0 赞/ 213 阅读

相关 python之sort(),sorted()

sort是容器的函数：sort(cmp=None, key=None, reverse=False) sorted是python的内建函数：sorted(iterab

左手的ㄟ右手/ 2022年06月05日 05:35/ 0 赞/ 192 阅读

相关 sort

文章目录 sort 默认排序sort file 忽略文本里面的相同行 -u 指定排序时所用的栏位分隔字符-t -k

我会带着你远行/ 2022年02月20日 15:11/ 0 赞/ 131 阅读

相关 Python3 排序 sort()、sorted()、sort(key=lambda)、sorted(key=lambda)

Python3 排序 sort()、sorted()、sort(key=lambda)、sorted(key=lambda) 初学者容易搞混，自己也是这两天整理一下网上搜

灰太狼/ 2021年05月12日 11:37/ 0 赞/ 559 阅读