前言:
眼前各位老铁们对“数据结构经典面试题”可能比较注意,兄弟们都需要学习一些“数据结构经典面试题”的相关资讯。那么小编同时在网摘上汇集了一些关于“数据结构经典面试题””的相关知识,希望你们能喜欢,咱们一起来学习一下吧!1、找到数组中缺失的第一个正整数
输入: [1,2,0]输出: 3-----输入: [3,4,-1,1]输出: 2-----输入: [7,8,9,11,12]输出: 1
思路:最直接的思路先对数组进行排序,可选择快速排序,时间复杂度O(nlog(n));空间复杂度O(1);然后对排序完的数组进行遍历(时间复杂度O(n)),即可得到第一个缺失的正整数。
进阶:
如果要求时间复杂度为O(n),空间复杂度不做要求,如何求解?
假设一共n个数,对其中的正数进行计数统计,放入到map中(时间复杂度O(n)),最多n个元素;从0开始,逐渐到n+1遍历,找到第一个对应计数为0的数,则直接返回,时间复杂度O(n);
这样时间复杂度O(n),空间复杂度O(n);
再进阶
如果要求时间复杂度为O(n),空间复杂度O(1),如何?
这里思路就非常巧妙了,首先判断1是否存在于数组中,如果不存在,直接返回;如果存在,则将所有负数和0替换为1;这时,所有元素均为正数;
然后逐元素进行遍历,对于>=n的元素不做处理,小于n的,比如a[0] = 3;那么将第三个位置a[3]的位置的数变为负号,这样既不丢失元素值,又可以表示3出现过;
遍历完之后,在进行一次遍历,第一个正数的位置即未出现的正整数。
寻找数组的众数
给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。可以假设数组是非空的,并且给定的数组总是存在众数。
输入: [3,2,3]输出: 3----输入: [2,2,1,1,1,2,2]输出: 2
思路1:利用hash表统计每一个数字出现的次数,然后对hash表进行遍历即可找到众数
时间复杂度和空间复杂度均为O(n)
思路2:众数的数量大于其他元素的数量,所以依次遍历,并且记录当前出现最多的数字以及出现的相对次数,这里的相对次数指的是众数的个数减去其他元素个数的总和,比如2,2,1,1,1,2,2;依次遍历得到的众数及相对次数为(2,1),(2,2),(2,1),(2,0),(1,1),(1,0),(2,1) 最终得到的众数为2,相对次数为1
两数之和 & 三数之和
给定一个数组,判断数组中是否存在两个元素之和等于给定值,如果存在,则返回对应的索引。
输入:[1,2,3,4] 目标值:6 2 + 4 = 6,返回[1,3]
思路:数组本身具有从索引转元素的功能,但是这里需要将值映射为索引;因为遍历到元素2的时候,需要知道数组中是否有4这个元素,如果有,应该返回其索引。所以先将数组转map,然后遍历即可;实际编码还可以进一步优化,如下:
进阶,扩展为三数之和:
思路:暴力解法是通过三次嵌套遍历,判断是否满足条件,这样时间复杂度为O(n^3),利用俩数之和的思路,可以将最后嵌套的遍历使用hash表实现,时间复杂度为O(n^2)
优化:基于上述思路进行优化,减少不必要的遍历,时间复杂度会得到优化,但仍为O(n^2)
首先对数组按照递增排序,基于排序后的数组进行遍历,减少不必要的遍历,比如:首先根据前两个数,计算出两数之和的最小值min2,那么第一层遍历时,遍历到目标值减去min2仍然大于0,这时候就没必要继续遍历了;第二层遍历时,如果遍历到两个数之和加上数组最小元素大于给定值,那么后面就不必要遍历了;
技术连载:开篇词
技术连载:连载提纲设计思路
技术连载:数据结构 - 数组