143. 排颜色 II
发布日期:2021-06-28 19:27:33
浏览次数:3
分类:技术文章
本文共 789 字,大约阅读时间需要 2 分钟。
143. 排颜色 II
给定一个有n个对象(包括k种不同的颜色,并按照1到k进行编号)的数组,将对象进行分类使相同颜色的对象相邻,并按照1,2,...k的顺序进行排序。
样例
样例1
输入:
[3,2,2,1,4]
4
输出:
[1,2,2,3,4]
样例2
输入:
[2,1,1,2,2]
2
输出:
[1,1,2,2,2]
挑战
一个相当直接的解决方案是使用计数排序扫描2遍的算法。这样你会花费O(k)的额外空间。你否能在不使用额外空间的情况下完成?
注意事项
- 不能使用代码库中的排序函数来解决这个问题
- k <= n
public class Solution {
/**
* @param colors: A list of integer
* @param k: An integer
* @return: nothing
*/
public void sortColors2(int[] nums, int k) {
int j=nums.length-1;
int flag = 0;
for (int i = 0; i < nums.length; ) {
if (nums[i] != flag) {
// System.out.println(i+","+nums[i]+","+flag);
while (nums[j] != flag) {
j--;
if (j<=i) {
flag++;
if (flag == k) return;
break;
}
}
if (j>i) {
// System.out.println(i+","+j);
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
}else{
j=nums.length-1;
}
}else{
i++;
}
}
}
}
转载地址:https://blog.csdn.net/xwdrhgr/article/details/116005042 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月08日 12时13分27秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
类的一些提问以及百度到的答案
2019-04-29
接口+配置文件+反射实现充值优惠
2019-04-29
职责链模式实现退卡
2019-04-29
yml格式(list)
2019-04-29
2019年最后一天
2019-04-29
2019年总结
2019-04-29
eureka和ribbon
2019-04-29
eureka重试机制
2019-04-29
Hystix
2019-04-29
feign的使用
2019-04-29
zuul的路径匹配
2019-04-29
zuul的权限拦截
2019-04-29
Vue报错
2019-04-29
通用异常处理
2019-04-29
pagehelper的使用
2019-04-29
要想成功先脱去幼稚
2019-04-29
代码规范
2019-04-29
学习了几个新词
2019-04-29
jdk8的特性stream().map()
2019-04-29
SpringBoot整合Spring Data Elasticsearch
2019-04-29