LintCode 排颜色 II题目分析代码

题目

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

注意事项

You are not suppose to use the library's sort function for this problem.

k <= n

样例 给出colors=[3, 2, 2, 1, 4],k=4, 你的代码应该在原地操作使得数组变成[1, 2, 2, 3, 4]

分析

其实就是排序,二分法排序

代码

class Solution {
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */
    public void sortColors2(int[] colors, int k) {
        if (colors == null || colors.length == 0) {
            return;
        }
        rainbowSort(colors, 0, colors.length - 1, 1, k);
    }
    
    public void rainbowSort(int[] colors,
                            int left,
                            int right,
                            int colorFrom,
                            int colorTo) {
        if (colorFrom == colorTo) {
            return;
        }
        
        if (left >= right) {
            return;
        }
        
        int colorMid = (colorFrom + colorTo) / 2;
        int l = left, r = right;
        while (l <= r) {
            while (l <= r && colors[l] <= colorMid) {
                l++;
            }
            while (l <= r && colors[r] > colorMid) {
                r--;
            }
            if (l <= r) {
                int temp = colors[l];
                colors[l] = colors[r];
                colors[r] = temp;
                
                l++;
                r--;
            }
        }
        
        rainbowSort(colors, left, r, colorFrom, colorMid);
        rainbowSort(colors, l, right, colorMid + 1, colorTo);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏静默虚空的博客

排序算法系列

概述 概念 排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。 排序分为内部排序和外部排序。 若整个排序过程不需要访问...

2297
来自专栏数据结构与算法

3110 二叉堆练习3

3110 二叉堆练习3 时间限制: 3 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 给定N...

2885
来自专栏一直在跳坑然后爬坑

RxJava2操作符之“Scan”作用示例用法运行结果分析总结

扫描,遍历,用法和上一个Reduce操作符差不多,只是这个操作符会将每一个过程的中间产物发射出来,而不是只发射结果

943
来自专栏数据结构与算法

洛谷P3273 [SCOI2011]棘手的操作

题目描述 有N个节点,标号从1到N,这N个节点一开始相互不连通。第i个节点的初始权值为a[i],接下来有如下一些操作:U x y: 加一条边,连接第x个节点和第...

3307
来自专栏大闲人柴毛毛

剑指 offer——面试题8求旋转数组的最小值

题目:将一个非递减序列的某一处切一刀,再把前半段序列放到后半段序列的后面,这样组成的新序列叫做“旋转数组”。要求获取一个旋转数组的最小值。 这本质上是一个求最值...

3476
来自专栏用户画像

7.6.2 内部排序算法的应用

1)若n较小(N<=50),则可以采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多,因而当记录本身信息量较大时,用简单选择排序...

701
来自专栏bboysoul

1165: C语言实验题――三个整数

描述:给出三个整数,请你设计一个程序,求出这三个数的和、乘积和平均数。 输入:输入只有三个正整数a、b、c。 输出:输出一行,包括三个的和、乘积、平均数。数...

994
来自专栏微信公众号:Java团长

Java泛型详解

定义了一个List类型的集合,先向其中加入了两个字符串类型的值,随后加入一个Integer类型的值。这是完全允许的,因为此时list默认的类型为Object类型...

1032
来自专栏五分钟学算法

五分钟学会一个很有用的排序:归并排序

由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画...

1794
来自专栏北京马哥教育

python3急速入门 (二) 列表的使用

云豆贴心提醒,这是马哥Linux运维Python3急速入门系列第1篇文章 列表用于组织其它数值,即写在方括号之间、用逗号分隔开的数值列表。列表内的项目不必全是...

2965

扫码关注云+社区

领取腾讯云代金券