数组统计分析-程序员宅基地

技术标签: 算法  数据结构与算法  

转载自:数组统计分析

给定数组A,大小为n,数组元素为1到n的数字,不过有的数字出现了多次,有的数字没有出现。请给出算法和程序,统计哪些数字没有出现,哪些数字出现了多少次。能够在O(n)的时间复杂度,O(1)的空间复杂度要求下完成么?


分析

这个题目,是有一定技巧的。技巧是需要慢慢积累,待经验多了之后,可以灵感或者直觉,就产生了技巧。如果不知道技巧,那该怎么办呢?

在开始分析之前,说明两个问题:

  • 原数组是没有排序的。如果排序了,很简单的。

  • O(1)的空间含义,可以使用变量,但不能开辟数组或者map等来计数。

这个题目,很直接的解法就是两层遍历,O(n^2)的复杂度,O(1)的空间。空间满足了,但是时间没有。

很多类似的题目,都会用XOR的方法,大家仔细想一下,这个题目,可以么?或者这个题目和可以用XOR的题目的差异在哪儿?最直接的就是,每一个数字的重复的次数是不同的。

还有就是以空间换时间的方法,例如用hash map或者数组来计数。时间满足了,但是空间没有满足。

那怎样才能有时间复杂度O(n),空间复杂度O(1)的算法呢?不能开辟新的空间,那么只剩下,重复利用数组A。那么该如何利用数组A呢?


首先,我们介绍一种三次遍历数组的方法,我们都考虑数组从0开始:

  • 第一次遍历:对于每一个A[i] = A[i] * n

  • 第二次遍历:对于每一个i,A[A[i]/n]++

  • 第三次遍历:对于每一个i,A[i] % n就是出现次数

A[i]应该出现在A中的A[i]位置,乘以n、再除以n,很容易的来回变换;第二次遍历,对于A[i]本来所在的位置不断增1,但绝对不对超出n的,那每一个i出现的次数,就是A[i]对n取余。

还有一种两次遍历的方法,也是上面的思路:题目中数组是1到n,为了方便算法考虑,以及数组存储方便,我们考虑0-n-1,结果是相同的。 考虑A[i],现在位置是i,如果采用A来计数,它的位置应该是A[i] % n,找到计数位置,该如何处理这个位置呢?加1么?显然不可以,这里有一个技巧,就是加n,有两个原因

  • 加n可以保证A[i] % n是不变的

  • A数组,最后每一个元素表示为A[i] = x + k*n,其中x<n,并且k就是我们要统计的频率。

上面的思路,转换为代码如下:


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

智能推荐

window 编程 -- Beep函数之祝你生日快乐!_祝你生日快乐beep函数输出-程序员宅基地

文章浏览阅读1.9k次。#include <Windows.h>int main(){ MessageBeep(MB_ICONHAND); MessageBeep(MB_ICONEXCLAMATION); MessageBeep(MB_ICONASTERISK); //system("pause"); while (1) {#if 1 Beep(523, 200); Beep(523, 200); Beep(578, 400); Beep(523, 400); Beep(698,._祝你生日快乐beep函数输出

阿里iconfont上传svg图片空白、或展示不全的解决方案/搜索到的icon无法改变颜色解决方案_sketch导出svg 为什么有一大片空白-程序员宅基地

文章浏览阅读1.4w次,点赞6次,收藏9次。原因造成这个问题的原因,可能是因为sketch、dx等软件在导出svg时,自动在svg上添加了一些iconfont平台无法解析的属性造成的。所以解决这个问题,要么从svg代码入手,要么就需要借助工具来完成。解决改代码并不是很理想的解决方式,这里我们借助iconfont官方平台推荐的图形设计软件AI来解决这个问题。1、首先下载一个AI软件2、然后使用AI打开通过其他设计软件导出的svg图标3、选中整个图标,然后选择对象—扩展—选择描边(已经选择取消,重新选择)——确定4、保存为svgsvg配置_sketch导出svg 为什么有一大片空白

一道verilog笔试题考察的generate特性_generate面试题-程序员宅基地

文章浏览阅读266次。生成语句可以动态的生成verilog代码,当对矢量中的多个位进行重复操作时,或者当进行多个模块的实例引用的重复操作时,或者根据参数的定义来确定程序中是否应该包含某段Verilog代码的时候,使用生成语句能大大简化程序的编写过程。生成语句生成的实例范围,关键字generate-endgenerate用来指定该范围。生成实例可以是以下的一个或多个类型:(1)模块;(2)用户定义原语;(3)门级语..._generate面试题

代码检测器、可重叠序列检测器、不可重叠序列检测器的区别_不可重复序列检测器-程序员宅基地

文章浏览阅读3.6k次,点赞6次,收藏18次。含义代码检测器检测的对象是依次输入的指定代码。检测时应按各代码的规定进行分组,组与组之间不能混淆(即不能重叠)。否则为序列检测器。简而言之,代码检测器要分段,序列检测器不用分段。例设有010代码检测器、010可重叠序列检测器、010不可重叠序列检测器,它们对于以下输入序列的检测结果:输入序列01001010000100代码检测器001..._不可重复序列检测器

使用torchvision.datasets.Imagefolder将数据分为训练集和测试集_imagefolder怎么分训练集与测试集-程序员宅基地

文章浏览阅读1.8k次,点赞2次,收藏10次。orig_set = torchvision.datasets.Imagefolder(...) # your datasetn = len(orig_set) # total number of examplesn_test = int(0.1 * n) # take ~10% for testtest_set = torch.utils.data.Subset(orig_set, range(n_test)) # take first 10%train_set = torch.util._imagefolder怎么分训练集与测试集

用flex布局实现左右两边对齐_flex布局左右两边-程序员宅基地

文章浏览阅读1.2w次。有这样的需求,文字左对齐,button右对齐。我们就可以用flex布局很好的实现此需求。代码如下:<html><head> <style type="text/css"> .wrapper{ width: 600px; border: 2px solid green; display: flex; flex-wrap: wrap; _flex布局左右两边

随便推点

WebStorm 之 Cordova 环境搭建_webstorm cordova 运行-程序员宅基地

文章浏览阅读554次。转发:https://www.cnblogs.com/xinaixia/p/6756779.html一、环境搭建  Cordova 环境配置之前,应先下载安装 Node.js ,中文官网:http://nodejs.cn/。  以管理员身份运行 cmd 命令行工具:  1、查看 Node.js 是否已安装成功,命令为:node -v  2、查看 npm 是否已安装,命令为:np..._webstorm cordova 运行

最新交易猫链接源码 带完整版教程_交易猫源码链接生成-程序员宅基地

文章浏览阅读957次。带一款非常简洁好看的后台。搭建教程:修改数据库账号密码直接使用。源码下载:下载地址网盘下载地址:https://pan.baidu.com/s/19iOsoyK-J-Rhi2dZYqzMMg?pwd=iumr提取码:iumr_交易猫源码链接生成

《论文笔记》CCM-SLAM: Robust and Efficient Centralized Collaborative Monocular SLAM for Robotic Teams_ccm_slam论文-程序员宅基地

文章浏览阅读1.1k次,点赞5次,收藏9次。《CCM-SLAM: Robust and Efficient Centralized Collaborative Monocular SLAM for Robotic Teams》作者:Patrik Schmuck,Margarita Chli单位:苏黎世联邦理工学院(ETH)期刊:Journal of Field Robotics(JFR)(二区)时间:2019摘要:机器人协作有望提高任务的鲁棒性和效率,在搜救和农业等领域具有巨大的应用潜力。多机器人协作同时定位和建图(SLAM)正是_ccm_slam论文

PCB(layout)常用快捷键_layout快捷键-程序员宅基地

文章浏览阅读1w次,点赞10次,收藏74次。快捷键的实用,极大的提高了大家工作中的效率,因此小编我特意帮大家搜集整理很多关于AD方面的常用快捷键,希望对大家有所帮助。一、PCB中常用快捷键R+L 输出PCB中所有网络的布线长度Ctrl+左键点击对正在布的线完成自动布线连接M+G 可更改铜的形状;按P+T在布线状态下,按Shift+A可直接进行蛇线走线T+R对已布完的线进行蛇线布线E++M+C点击空白出可迅速找到PCB上想要的元件Backsp..._layout快捷键

HTTP1.1 和 HTTP2.0 的区别_描述http2.0与http1.2的不同-程序员宅基地

文章浏览阅读2.1k次。1、内容安全,因为http2.0是基于https的,天然具有安全特性,通过http2.0的特性可以避免单纯使用https的性能下降;2、二进制格式,http1.X的解析是基于文本的,http2.0将所有的传输信息分割为更小的消息和帧,并对他们采用二进制格式编码,基于二进制可以让协议有更多的扩展性,比如引入了帧来传输数据和指令;3、多路复用,这个功能相当于是长连接的增强,每个request请求可以随机的混杂在一起,接收方可以根据request的id将request再归属到各自不同的服务端请求里面,另外多路_描述http2.0与http1.2的不同

python中怎么随机从字典中取值_python怎样从字典中随机取数据-程序员宅基地

文章浏览阅读1w次,点赞5次,收藏16次。python从字典中随机取数据的方法:可以利用random.sample()函数来实现。random.sample()函数多用于截取列表的指定长度的随机数,但是不会改变列表本身的排序。random.sample()函数返回从总体序列或集合(potution)中选择的唯一元素的 k 长度列表(list),多用于截取列表的指定长度的随机数,但是不会改变列表本身的排序。代码实现:import rando..._字典随机取值

推荐文章

热门文章

相关标签