如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)_对n个整数进行排序要求时间复杂度为on空间复杂度为o1-程序员宅基地

技术标签: 每日算法  

咋一看会觉得没有办法实现,因为所有的排序方法都无法满足该时间复杂度o(n)和空间复杂度o(1)。

但是如果n是有限的,其实是有办法可解的:假设n 没有超过int的最大值 ,0<n<65536 这里我们暂时不考虑为负数的情况(负数也可解)。

可以定义一个大小为65535的数组,遍历n个元素,以其值做索引,值为出现的个数

0 -》 array[0]++;

1 -》 array[1]++;

....

 

再遍历array数组,根据array数组打印出现个数大于0的下标,打印的次数为该下标的值



版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/yangzheng110/article/details/52980340

智能推荐

C++报错无效的预处理命令include_【零基础C语言】- 预处理指令1 - 宏定义!-程序员宅基地

文章浏览阅读339次。预处理指令简介1.C语言在对源程序进行编译之前,会先对一些特殊的预处理指令作解释(比如之前使用的#include文件包含指令),产生一个新的源程序(这个过程称为编译预处理),之后再进行通常的编译2.为了区分预处理指令和一般的C语句,所有预处理指令都以符号"#"开头,并且结尾不用分号3.预处理指令可以出现在程序的任何位置,它的作用范围是从它出现的位置到文件尾。习惯上我们尽可能将预处理指令写在源程序开..._c++ 命令行错误: 宏定义无效: thread exceptions rtti stl

linux输入子系统(设备驱动与事件驱动)_linux轨迹球鼠标驱动-程序员宅基地

文章浏览阅读4.1k次。内核的输入子系统是为了对分散的、多种不同类别的输入设备(如键盘、鼠标、轨迹球、操纵杆、辊轮、触摸屏、加速计和手写板)进行统一处理的驱动。输入子系统带来了如下好处: • 统一了物理形态各异的相似的输入设备的处理功能。例如,各种鼠标,不论PS/2、USB,还是蓝牙,都被同样处理。 • 提供了用于分发输入报告给用户应用程序的简单的事件(event)接口。你的驱动不必创建、管理_linux轨迹球鼠标驱动

Arduino实现流水灯效果_ard流彩灯程序-程序员宅基地

文章浏览阅读4.6k次,点赞7次,收藏24次。Arduino实现流水灯效果int NUM = 6; //LED 灯的总数void setup(){for (int i = BASE; i < BASE + NUM; i ++){pinMode(i, OUTPUT); //设定数字i引脚为输出}}void loop(){for (int i = BASE; i < BASE + NUM; i ++){..._ard流彩灯程序

Android中的LayoutInflater和inflate-程序员宅基地

文章浏览阅读54次。1、inflate方法inflate()作用就是将xml定义的一个布局找出来,但仅仅是找出来而且隐藏的,没有找到的同时并显示功能。android上还有一个与Inflate()类似功能的方法叫findViewById(),二者有时均可使用,但也有区别: 如果你的Activity里用到别的layout,比如对话框layout,你还要设置这个layout上的其他组件的内容,你就必..._android studio layoutinflater报错

我的友情链接-程序员宅基地

文章浏览阅读31次。51CTO博客开发西蒙[爱生活,爱学习]NEW TIME! NEW WAY!::知讯者生存::晓翼的blog岳雷的微软网络课堂Kirin的茶水间苏繁的博客脚本中心虚拟的现实矩阵天空快乐分享胖哥技术堂Chao_SpaceIT技术交流越野苍狼的博客努力学习的小熊echo@officeabner kou城市猎人叶俊坚许一君的原创技术博客北京动点飞扬技术开发团队张选波博客激情因梦想而...

基于Java电脑硬件库存管理系统设计实现(源码+lw+部署文档+讲解等)_java计算机硬件管理系统-程序员宅基地

文章浏览阅读1.1w次,点赞6次,收藏6次。互联网发展至今,无论是其理论还是技术都已经成熟,而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播,搭配信息管理工具可以很好地为人们提供服务。针对电脑硬件库存信息管理混乱,出错率高,信息安全性差,劳动强度大,费时费力等问题,采用电脑硬件库存管理系统可以有效管理,使信息管理能够更加科学和规范。电脑硬件库存管理系统在Eclipse环境中,使用Java语言进行编码,使用Mysql创建数据表保存本系统产生的数据。_java计算机硬件管理系统

随便推点

anaconda+pycharm配置tensorflow-GPU环境最简单方法_pycharm如何用显卡运行-程序员宅基地

文章浏览阅读2.1k次,点赞3次,收藏6次。2018年开始学习tensorflow框架。买了块显卡1060 6G。装上了原生的ubuntu16.04。从安装显卡驱动到cuda和cudnn。无奈配置tensorflow环境一直报错。之后转回windows系统。试着继续用网上说的命令行配置,还查了tensorflow的官方文档。还是报错。最后用最简单的anaconda navigator配置成功。前后不到2个小时。下面说下步骤。首先..._pycharm如何用显卡运行

在ASP.NET应用启动的时候初始化的几种方法_.net页面初始化函数是哪个-程序员宅基地

文章浏览阅读1.2k次。ASP.NET 4.0 之前,有两种方法:通过Global.asax 中的 Application_Start 事件启动,或者通过定义在 App_Code 文件夹中任意类中的AppInitialize 静态方法。方法的原型定义如下:public static void AppInitialize() AppInitialize 方法是 ASP.NET 中一个特殊的方法,在网站应用程序启动之_.net页面初始化函数是哪个

底层进阶 | 移动端 GPU 架构 -- TBR 模型-程序员宅基地

文章浏览阅读1.3k次。在知乎上关注了好多图形学大佬,感觉现在知乎的技术氛围要比掘金推荐旧文好多了,经常会推送感兴趣的领域内容,而且还可以和作者私信交流。这段时间看到有大佬分享 GPU 架构相关的内容,做图像渲染..._tbr

WIN10 控制台cmd乱码及永久修改编码的解决办法_win10控制台乱码-程序员宅基地

文章浏览阅读1.8w次,点赞14次,收藏40次。WIN10 cmd控制台本来的编码是ANSI的,所以要求执行的批处理脚本编码格式也是ANSI才行,要不就两边统一都改成UTF-8处理(作为一个程序员,一般我都会统一成UTF-8编码格式),下面就介绍如何统一改成UTF-8编码格式一、修改控制台CMD编码格式为UTF-8我本机的系统环境:OS Name: Microsoft Windows 10 企业版OS Version: 1..._win10控制台乱码

服务器无法识别url中特殊字符的处理方式_java 服务 url地址[]识别不出来-程序员宅基地

文章浏览阅读1.9k次。url出现了有+,空格,/,?,%,#,&,=等特殊符号的时候,可能在服务器端无法获得正确的参数值,如何是好?解决办法将这些字符转化成服务器可以识别的字符,对应关系如下:URL字符转义特殊符号 url中含义 字符转义+ URL 中+号表示空格 %2B空格 URL中的空格可以用+号..._java 服务 url地址[]识别不出来

msp432p401r 编码器电机程序_星海中的绿洲csdn-程序员宅基地

文章浏览阅读7.1k次,点赞21次,收藏143次。msp432p401r的评估板也到了一段时间了,刚好最近有时间学习432。在看b站up主RNA的432教程的时候看到有人不懂编码器电机的程序,刚好本人电赛又倾向做控制题所以开发了这个程序,和大家交流学习一下。 编码器电机的原理网上有很多,如果不懂可以看下这个博主的文章STM32应用(九)编码器及其测速原理、L298N电机驱动控制编码器电机_長空雁的博客-程序员宅基地 在这里博主只讨论如何去用软件采集测速。外部中断采集脉冲编码器的AB相会输出方波,因..._星海中的绿洲csdn

推荐文章

热门文章

相关标签