导语：技术连载：数据结构 - 数组常见面试题汇总

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，这时候就没必要继续遍历了；第二层遍历时，如果遍历到两个数之和加上数组最小元素大于给定值，那么后面就不必要遍历了；

三数之和

技术连载：开篇词

技术连载：连载提纲设计思路

技术连载：数据结构 - 数组

本文内容由小苹整理编辑！