Sort Colors — LeetCode「建议收藏」

Sort Colors — LeetCode

大家好,又见面了,我是全栈君。

原题链接: 
http://oj.leetcode.com/problems/sort-colors/
 


这道题也是数组操作的题目。事实上就是要将数组排序,仅仅是知道数组中仅仅有三个元素0,1,2。熟悉
计数排序
的朋友可能非常快就发现这事实上就是使用计数排序,元素空间仅仅须要三个元素就可以。代码例如以下: 

public void sortColors(int[] A) {
    if(A==null || A.length==0)
        return;
    int[] res = new int[A.length];
    int[] helper = new int[3];
    for(int i=0;i<A.length;i++)
    {
        helper[A[i]]++;
    }
    for(int i=1;i<3;i++)
    {
        helper[i]=helper[i]+helper[i-1];
    }
    for(int i=A.length-1;i>=0;i--)
    {
        res[helper[A[i]]-1] = A[i];
        helper[A[i]]--;
    }
    for(int i=0;i<A.length;i++)
    {
        A[i] = res[i];
    }
}

上面的代码是计数排序的标准解法。能够看到总共进行了三次扫描,事实上最后一次仅仅是把结果数组拷贝到原数组而已。假设不须要in-place的结果仅仅须要两次扫描。


事实上就算返回元素组也能够是两次扫描,这须要用到元素仅仅有0,1,2的本质。我们知道helper[i]中是包括着0,1,2的元素数量,我们仅仅须要依照helper[0,1,2]的数量依次赋值过来就可以(每层循环把helper[i]–,假设helper[i]到0就i++就能够了)。仅仅是这样就不是计数排序比較标准的解法,我希望还是复习一下。


这样的方法的时间复杂度是O(2*n),空间是O(k),k是颜色的数量,这里是3。


上述方法须要两次扫描。我们考虑怎么用一次扫描来解决。事实上还是利用了颜色是三种这一点,道理事实上也简单。就是搞两个指针。一个指在当前0的最后一个下标,还有一个是指在当前1的最后一个下标(2不须要指针由于剩下的都是2了)。进行一次扫描,假设遇到0就两个指针都前进一步并进行赋值,假设遇到1就后一个指针前进一步并赋值。代码例如以下: 

public void sortColors(int[] A) {
    if(A==null || A.length==0)
        return;
    int idx0 = 0;
    int idx1 = 0;
    for(int i=0;i<A.length;i++)
    {
        if(A[i]==0)
        {
            A[i] = 2;
            A[idx1++] = 1;
            A[idx0++] = 0;
        }
        else if(A[i]==1)
        {
            A[i] = 2;
            A[idx1++] = 1;
        }
    }
}

上述方法时间复杂度还是O(n)。仅仅是仅仅须要一次扫描,空间上是O(1)(假设颜色种类是已知的话)。


这道题我认为主要还是熟悉一下计数排序计数排序是线性排序中比較重要的一种,关于排序要搞个专题专门的复习一下。非常多排序的基本思想都对解题有帮助哈。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116155.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 手把手教你搭建Android开发环境

    手把手教你搭建Android开发环境搭建开发环境,是学习一门技术的开始。参照网上的教程,整理了一下。进行Android开发应用开发时,首先需要有JDK和AndroidSDK的支持,还需要开发工具。在AndriodStudio2.2开始,安装AndroidStudio时,会自动安装JDK和AndroidSDK。下载网址:https://developer.android.google.cn/studio/一、进入网址,点击下载安卓工作室(原英文版,翻译后的界面了)二、点击下载后,出现协议界面,勾选同意,下载。三、双击刚

  • 微服务分布式事务解决方案_微服务追踪与监控

    微服务分布式事务解决方案_微服务追踪与监控目录Sleuth简介相关术语使用Sleuth引入依赖创建服务product-serviceorder-service启动&测试Zipkin使用Zipkin参考文章Sleuth简介Sleuth是SpringCloud的组件之一,它为SpringCloud实现了一种分布式追踪解决方案,兼容Zipkin,HTrace和其他基于日志的追踪…

    2022年10月28日
  • redis实现单点登录原理(spring ioc和aop原理及应用场合)

    单点登录功能分析请求的url:/user/login请求的方法:POST参数:username、password,表单提交的数据。可以使用方法的形参接收。返回值:json数据,包含一个token。业务逻辑:登录的业务流程:登录的处理流程:1、登录页面提交用户名密码。2、登录成功后生成token。Token相当于原来的sessionid,字符串,可以使用uuid。3、把

  • jnpf开发文档_java开发最新技术

    jnpf开发文档_java开发最新技术JNPF快速开发平台JNPF快速开发平台采用前后端分离技术、采用B/S架构开发,形成一站式开发多端(APP+PC)使用。使用JNPF开发平台可以简单、快速、高效的构建各种类型java项目。JAVA版介绍JNPF.java版采用前后端分离,可将代码直接导入idea运行,也可将前后端代码利用ngnix分开部署。JNPF主体架构、技术采用前后端分离技术,主体架构为B/S,PC端和APP混合开发。前后端分离特点JNPF快速开发平台平台采用全新的前后端分离架构模式。前…

  • linux多进程与进程间通信_linux共享内存进程间通信

    linux多进程与进程间通信_linux共享内存进程间通信Linux下进程间通信–共享内存:最快的进程间通信方式

    2022年10月10日
  • MySQL安装出问题

    MySQL安装出问题

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号