143. 排颜色 II-白红宇的个人博客

143. 排颜色 II

发布日期：2021-06-28 19:27:33 浏览次数：4 分类：技术文章

本文共 789 字，大约阅读时间需要 2 分钟。

143. 排颜色 II

给定一个有n个对象（包括k种不同的颜色，并按照1到k进行编号）的数组，将对象进行分类使相同颜色的对象相邻，并按照1,2，...k的顺序进行排序。

样例

样例1

输入:

[3,2,2,1,4]

输出:

[1,2,2,3,4]

样例2

输入:

[2,1,1,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 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：144. 交错正负数

下一篇：142. O(1)时间检测2的幂次

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

143. 排颜色 II

样例

挑战

注意事项

发表评论

最新留言

关于作者

推荐文章