【2018年数据结构真题】

方法一

给定一个含n(n>=1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组{-5,3,2,3}中未出现的最小正整数是1;数组{1,2,3}中未出现的最小正整数是4。要求:

  1. 给出算法的基本设计思想。

  2. 根据设计思想,采用C或C++语言描述算法,关键之 处给出注释。

  3. 说明你所设计算法的时间复杂度和空间复杂度。

读完题目先找关键词,这里可以直接提取这样几个关键词

  • 使用数组,求未出现的最小正整数
  • 看到数组,是不是想到是否有序
  • 时间+空间尽可能高效

暴力解:快速排序,然后扫描一遍数组

先对数组A快速排序得到升序序列,然后遍历数组找到第一个未出现的最小正整数。

void Qsort(int A[], L, R){      //a数组保存数据,L和R是边界if (L>=R) return;      //当前区间元素个数<=1则退出int key, i=L, j=R;     //i和j是左右两个数组下标移动//把a数组中随机一个元素和A[L]交换,快排优化,使得基准值的选取随机key=A[L]; //key作为枢值参与比较while (i<j){while (i<j && A[j]>key) j--;while (i<j && A[i]<=key) i++;if (i<j) swap(A[i], A[j]); //交换A[i]和A[j]}swap(A[L], A[i]);Qsort(A, L, i-1); //递归处理左区间Qsort(A, i+1, R); //递归处理右区间}void ans(int A[], n){ //算法代码Qsort(A, 0, n-1);int i=0;while (i<n && A[i]<=0) i++;if (i==n){ //数组A全是非正数cout<<1;//输出1 return;}/*到这里,A[i]是数组中最小的正数*/ int t=1;//t从1开始for (int j=i; j<n; j++){ if (t==A[j])continue; if (t+1==A[j])t++;else{ //t+1空缺cout<<t+1; //输出j-i+1 return;}cout<<t+1;//遍历完数组,输出t+1}
}

方法二

解析:

思想借鉴到了 Counting sort 中的方法。既然不能用额外空间,那就只有利用
数组本身,跟 Counting sort 一样,利用数组的 index 来作为数字本身的索引,把正
数按照递增顺序依次放到数组中。即让 A[0]=1, A[1]=2, A[2]=3, … , 这样一来,
最后如果哪个数组元素违反了 A[i]=i+1 即说明 i+1 就是我们要求的第一个缺失的正
数。对于那些不在范围内的数字,我们可以直接跳过,比如说负数,0,或者超过数组
长度的正数,这些都不会是我们的答案。

思路:

交换数组元素,使得数组中第 i 位存放数值(i+1)。最后遍历数组,寻找第一
个不符合此要求的元素,返回其下标。整个过程需要遍历两次数组,复杂度为 O(n)。
下图以题目中给出的第二个例子为例,讲解操作过程。

image.png

public int firstMissingPositive(int []A){if(A==null||A.length==0){return 1;}for(int i=0;i<A.length;i++){if(A[i]<=A.length && A[i]>0 && A[A[i]-1]!=A[i]){int temp = A[A[i]-1];A[A[i]-1] = A[i];A[i] = temp;i--;}}for(int i=0;i<A.length;i++){it(A[i]!=i+1)return i+1;}return A.length+1;
}

实现中还需要注意一个细节,就是如果当前的数字所对应的下标已经是对应数字了,
那么我们也需要跳过,因为那个位置的数字已经满足要求了,否则会出现一直来回交
换的死循环。这样一来我们只需要扫描数组两遍,时间复杂度是 O(2*n)=O(n),而且
利用数组本身空间,只需要一个额外变量,所以空间复杂度是 O(1)。

补充

Counting sort 基本思想

对于给定的输入序列中的每一个元素 x,确定该序列中值小于 x 的元素的个数 。一
旦有了这个信息,就可以将 x 直接存放到最终的输出序列的正确位置上。它创建一个
长度为这个数据范围的数组 C,C 中每个元素记录要排序数组中对应记录的出现个
数。

下面以示例来说明这个算法:

假设要排序的数组为 A = {1,0,3,1,0,1,1}这里最大值为 3,最小值为 0,那么我们
创建一个数组 C,长度为 4。

然后一趟扫描数组 A,得到 A 中各个元素的总数,并保持到数组 C 的对应单元中。比如 0 的出现次数为 2 次,则 C[0] = 2;1 的出现次数为4 次,则 C[1] = 4。由于 C 是以 A 的元素为下标的,所以这样一做,A 中的元素在 C中自然就成为有序的了,这里我们可以知道 顺序为 0,1,3 (2 的计数为 0)然后我们把这个在 C 中的记录按每个元素的计数展开到输出数组 B 中,排序就完成了。

也就是 B[0] 到 B[1] 为 0 B[2] 到 B[5] 为 1 这样依此类推。
这种排序算法,依靠一个辅助数组来实现,不基于比较,算法复杂度为 O(n) ,但由
于要一个辅助数组 C,所以空间复杂度要大一些,由于计算机的内存有限,所以这种
算法不适合范围很大的数的排序。

上述为计数排序算法的经典解法,不过这个解法并不是最优的,因为空间复杂度还应
该可以优化,我们完全可以不要那个输出的数组 B,直接对 C 进行排序。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/201301.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

算法刷题-动态规划2

算法刷题-动态规划2 珠宝的最高价值下降路径最小和 珠宝的最高价值 题目 大佬思路 多开一行使得代码更加的简洁 移动到右侧和下侧 dp[ i ][ j ]有两种情况&#xff1a; 第一种是从上面来的礼物最大价值&#xff1a;dp[ i ][ j ] dp[ i - 1 ][ j ] g[ i ][ j ] 第二种是从左…

常见的8个JMeter压测问题

为什么在JMeter中执行压力测试时&#xff0c;出现连接异常或连接重置错误&#xff1f; 答案&#xff1a;连接异常或连接重置错误通常是由于服务器在处理请求时出现问题引起的。这可能是由于服务器过载、网络故障或配置错误等原因导致的。 解决方法&#xff1a; 确定服务器的…

【高级网络程序设计】Week3-2 Servlet

一、 What are servlets? 1. 定义 &#xff08;1&#xff09;Servlets are Java’s answer to CGI&#xff1a; programs that run on a web server acting as middle layer between HTTP request and databases or other applications.Used for client requests that cann…

【LeetCode刷题】-- 29.两数相除

29.两数相除 思路&#xff1a; class Solution {public int divide(int dividend, int divisor) {//考察被除数为最小值的情况if(dividend Integer.MIN_VALUE){//被除数为最小值&#xff0c;除数是1&#xff0c;返回最小值if(divisor 1){return Integer.MIN_VALUE;}//除数是-…

羊大师提示,羊奶都有哪些惊人功效?

羊奶不仅是一种美味的健康饮品&#xff0c;在近年来备受瞩目的的健康圈子里&#xff0c;羊奶还被赋予了更多的功效&#xff0c;成为一种备受推崇的保健品。羊奶不但富含营养&#xff0c;而且还有着非常多的益处&#xff0c;它能够用来美容、保健&#xff0c;甚至还可以治疗某些…

C语言基本算法之选择排序

目录 概要&#xff1a; 代码如下 运行结果如下 概要&#xff1a; 它和冒泡排序一样&#xff0c;都是把数组元素按顺序排列&#xff0c;但是方法不同&#xff0c;冒泡排序是把较小值一个一个往后面移&#xff0c;选择排序则是直接找出最小值&#xff0c;可以这个说&#xff…

【OpenCV实现图像:OpenCV利用Python创作热力图】

文章目录 概要读取图像图像灰度化**像素化效果**小结 概要 热力图是一种强大的统计图表&#xff0c;通过对数据进行色彩映射&#xff0c;直观展示了数据分布的热度和密度。在绘制热力图时&#xff0c;关键在于指定颜色映射的规则&#xff0c;这决定了图中不同数值的呈现方式。…

【React-Router】路由导航

1. 概念 路由系统中的多个路由之间需要进行路由跳转&#xff0c;并且在跳转的同时有可能需要传递参数进行通信。 2. 声明式导航 // /page/Login/index.jsimport { Link } from react-router-dom const Login () > {return <div>登录页{/* 解析成 a 链接 */}<Li…

利用ros实现单片机通讯(转载)

我觉得如果使用这个人的micro_ros通信协议&#xff0c;就不用再去Ubuntu或者Windows上面自己写驱动程序了&#xff0c; 利用micro_ros实现esp32与ros2的通讯 Tianci ​ 天津大学 工学博士 参考&#xff1a;https://github.com/micro-ROS/micro_ros_arduino https://blog.cs…

04 后端增删改查【小白入门SpringBoot + Vue3】

项目笔记&#xff0c;教学视频来源于B站青戈 https://www.bilibili.com/video/BV1H14y1S7YV 保证前面的都功能都实现后&#xff0c;接着往下走。 查 分页 接下来&#xff0c;实现前端页面分页功能。 前端分页组件 打开elementplus官网&#xff0c;找到合适的分页组件&…

软件测试工具常用的都有哪些

软件测试工具是用于辅助软件测试的软件工具&#xff0c;可以帮助测试人员执行测试用例、记录测试结果、跟踪缺陷状态等&#xff0c;提高测试效率和质量。以下是一些常见的软件测试工具&#xff1a; 一、AutoRunner自动化测试工具 AutoRunner(简称AR&#xff09;是国内自主研发…

python使用selenium webDriver时 报错

可能原因和解决&#xff1a; 1. python 解释器 ----> 设置 2. 浏览器版本 与 浏览器驱动版本不一致 ----> 安装同一版本的 (下载chromedriver | 谷歌驱动更高版本的测试版) 参考&#xff1a;Python使用Selenium WebDriver的入门介绍及安装教程-CSDN博客 Selenium安…

企业网盘哪家好?值得信赖的品牌推荐

企业网盘可谓是当下热门的企业服务之一&#xff0c;市面上也出现了非常多企业网盘工具。那么&#xff0c;企业网盘哪家好&#xff1f;哪个品牌更值得信赖呢&#xff1f; 企业网盘哪家好&#xff1f; Zoho Workdrive企业网盘一定榜上有名&#xff0c;Zoho Workdrive企业网盘是著…

IDEA JRebel安装使用教程

1、下载插件 版本列表&#xff1a;https://plugins.jetbrains.com/plugin/4441-jrebel-and-xrebel/versions 下载&#xff1a;JRebel and XRebel 2022.4.1 这里下载2022.4.1版本&#xff0c;因为后续新版本获取凭证会比较麻烦。下载完成会是一个压缩包。 2、安装 选择第一步…

微软Copilot即将对大陆开放,一起来看看都有什么好用的功能

微软发布了Copilot&#xff0c;12月1日起对大陆用户开放&#xff0c;以下是Copilot的11个新功能&#xff0c;你一定不想错过&#xff1a;1. PowerPoint&#xff1a; 将Word文档转换为演示文稿。从文件中快速创建演示文稿。通过关键幻灯片总结冗长的演示文稿。使用提示添加新的…

2024贵州大学计算机考研分析

24计算机考研|上岸指南 贵州大学 贵州大学计算机科学与技术学院&#xff08;贵州大学省级示范性软件学院&#xff09;位于贵州省贵阳市花溪区贵州大学东校区。 计算机科学与技术学院&#xff08;软件学院&#xff09;自1972年创办计算机软件本科专业开始&#xff0c;至今已有…

cadence layout lvs时出现error

Error&#xff1a;Schematic export failed or was cancelled.Please consult the transcript in the viewer window. 解决办法同下&#xff1a; cadence layout lvs时出现error-CSDN博客

Unity 头顶图文字性能优化

如图&#xff1a;常规的排版&#xff0c;会有很多Batches。这是优化后的Batches只有3。 常用解决方案&#xff1a; 1、创建两个Canvas&#xff0c;一个放所有文本Text&#xff0c;一个放所有Image。但这里有会有两个问题&#xff1a;一旦文字夹在两个Image中间&#xff0c;还有…

掌握Katalon Studio 导入 swagger 接口文档,接口测试效率提升100%

katalon studio大家都已经不陌生了&#xff0c;是一款现在非常主流的自动化测试工具&#xff0c;包括了web、api、APP&#xff0c;甚至PC应用程序都可以使用它来完成自动化测试。 swagger是一款RESTFUL接口的文档在线自动生成软件&#xff0c;swagger是一个规范和完整的框架&a…

智能座舱架构与芯片 - (2) 架构篇

一、定义 1.1 智能座舱定义 按照百度百科的定义&#xff0c;智能座舱&#xff08;intelligent cabin&#xff09;旨在集成多种IT和人工智能技术&#xff0c;打造全新的车内一体化数字平台&#xff0c;为驾驶员提供智能体验&#xff0c;促进行车安全。目前国内外已经有很多研究…