作者介绍：Runsen目前大三下学期，专业化学工程与工艺，大学沉迷日语，Python， Java和一系列数据分析软件。导致翘课严重，专业排名中下。.在大学60%的时间，都在CSDN。决定今天比昨天要更加努力。

从大一写Python文章，到现在其都有上百篇，现在到了六十五，今日主要写的是数据结构中的数组 Array

数组 Array

在平时使用最多的恐怕就是数组了吧，它是使用最广泛的一种数据结构，它是相同数据类型（可以是基本类型也可以是自定义类型）的元素按一定顺序排列的集合，它们在内存中按照这个先后顺序连续存放在一起。有一维数组，二维数组，多维数组。通俗的理解就是我们一般把一群羊或者一群牛放在一个圈里面，这个圈就相当于数组容器，每一个羊相当于一个元素。

查询 Access: O(1) 插入 Insert: 平均 O(n) 删除 Delete: 平均 O(n)

优点：

有序 可以进行下标操作，随机访问效率很高，时间复杂度可以达到O(1) 添加速度快 缺点： 删除，删除第一个，删除最后一个，选择一个位置删除这些都不方便操作 在数组起始位置处，插入数据和删除数据效率低，时间复杂度平均 O(n) 内存空间要求高，必须有足够的连续的内存空间

题目

这是争哥的春节天天练，那时我太菜了。没搞。

三数之和

leetcode 三数之和，这是Leecode的第十五道题目。

https://leetcode-cn测试数据/problems/3sum/Majority

 #给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c =?0?？请你找出所有满足条件且不重复的三元组。? # #?注意：答案中不可以包含重复的三元组。?  #?示例：? # #?给定数组?nums?=?[-1,?0,?1,?2,?-1,?-4]， # #满足要求的三元组集合为： #[ #??[-1,?0,?1], #??[-1,?-1,?2] #] 注意：答案中不可以包含重复的三元组。  

三数之和就当两数来干，两次遍历，判断第三个数在不在，就是时间复杂度。

 def?threeSum(nums): ????result?=?[] ????nums.sort() ????a?=?len(nums) ????for?i?in?range(a?-?1): ????????for?j?in?range(i?+?1,?a): ????????????if?-(nums[i]?+?nums[j])?in?nums[j?+?1:]: ????????????????array?=?[nums[i],?nums[j],?-(nums[i]?+?nums[j])] ????????????????if?array?not?in?result: ????????????????????result.append(array) ????return?result nums?=?[-1,?0,?1,?2,?-1,?-4] print(threeSum([-1,?0,?1,?2,?-1,?-4]))  

但是会超出时间，其实三数之和用的不是这样子的，做法是双指针。

我们可以先把这个数组进行从小到大的排序，因为排序的复杂度是远远小于的，排序后，你会发现，由于三数之和是等于零，那么如果当前这个元素是大于零的话，而且，这个数组是按照从小到大排序的话，那么当前这个元素作为起点的集合是为空的，因为后面的元素都是比这个元素大的元素，是不可相加等于零。

由此我们可以节省一些复杂度，当然，我们进行排序的时候，是要经历一些复杂度的，但这远远小于n的平方，所以我们这个做法还是比较快的。

然后我们在确定起点之后，通过双指针去遍历其他两个元素。

看不懂看下面的图片

 def?threeSum(nums): ????nums.sort() ????#?[-4,?-1,?-1,?0,?1,?2] ????res_list?=?[] ????#?头部循环查找 ????for?i?in?range(len(nums)): ????????if?i?==?0?or?nums[i]?>?nums[i?-?1]: ????????????#?最左端 ????????????l?=?i?+?1 ????????????#?最右端 ????????????r?=?len(nums)?-?1 ????????????while?l?<?r:??#?正在查找 ????????????????three_sum?=?nums[i]?+?nums[l]?+?nums[r] ????????????????if?three_sum?==?0: ????????????????????res_list.append([nums[i],?nums[l],?nums[r]]) ????????????????????l?+=?1??#?右移一位 ????????????????????r?-=?1??#?左移一位 ????????????????????while?l?<?r?and?nums[l]?==?nums[l?-?1]: ????????????????????????#?从左往右，相同数值直接跳过 ????????????????????????l?+=?1 ????????????????????while?r?>?l?and?nums[r]?==?nums[r?+?1]: ????????????????????????#?从右往左，相同数值直接跳过 ????????????????????????r?-=?1 ????????????????elif?three_sum?>?0: ????????????????????#?大于零，右边数值大，左移 ????????????????????r?-=?1 ????????????????else: ????????????????????#?小于零，左边数值小，右移 ????????????????????l?+=?1 ????return?res_list  

求众数

题目来源于 LeetCode 上第 169 号问题：求众数（求数组中超过一半的数字）。题目难度为 Easy

 #给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于?? n/2 ??的元素。? # #?你可以假设数组是非空的，并且给定的数组总是存在多数元素。? #?示例?1:? # #?输入:?[3,2,3] #输出:?3? # #?示例?2:? # #?输入:?[2,2,1,1,1,2,2] #输出:?2 #? #?Related?Topics?位运算?数组?分治算法  

方法：遍历整个数组，出现次数比其他数字加起来出现次数还多的元素返回。

最简单的方法就排序，取出 ? n/2 ? 的元素

 def?majorityElement(self,?nums): ????nums.sort() ????return?nums[int(len(nums)?/?2)]  

然后一种计数的方法，用字典来储存起来。

 class?Solution(object): ????def?majorityElement(self,?nums): ????????""" ????????:type?nums:?List[int] ????????:rtype:?int ????????""" ????????num?=?{} ????????for?i?in?nums: ????????????if?i?in?num: ????????????????num[i]?+=?1 ????????????else: ????????????????num[i]?=?1 ????????return?max(num.items(),key?=?lambda?x:x[1])[0]  

还可以直接使用collections

 import?collections  def?majorityElement(self,?nums): ?????return??collections.Counter(nums).most_common()[0][0]  

求缺失的第一个正数

题目来源于 LeetCode 上第 41 号问题：求缺失的第一个正数

中文版：https://leetcode-cn测试数据/problems/first-missing-positive/

 #给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。? #?示例?1:? # #?输入:?[1,2,0] #输出:?3 # #?示例?2:? # #?输入:?[3,4,-1,1] #输出:?2 #? #?示例?3:? # #?输入:?[7,8,9,11,12] #输出:?1 #?提示：? # #?你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。? #?Related?Topics?数组   

这道题的难度在于时间和空间的限制。

若没有时间的限制，可以直接排序后遍历查找。

若没有空间的限制，可以创建辅助空间后记录。

最简单的做法就是出现就+1。

题目的要求是找到没有出现过的最小正整数，最小的正整数是1，如果1没出现过，那么答案就是1，否则，自增1，继续看2是否在列表中。

 class?Solution: ????def?firstMissingPositive(self,?nums:?List[int])?->?int: ????????res?=?1 ????????while?res?in?nums: ????????????res?+=?1 ????????return?res   

把数组里 所有>=1的元素 放在它该放的位置！哪里是该放的位置? ：放在值减一的位置 例如，数组［4 1 5 -1 2］。4应该放在下标为3(4-1)的位置，交换后 ［-1 1 5 4 2］ 1应该放在下标为0(1-0)的位置，交换后 ［1 -1 5 4 2］ 以此类推 ［1 -1 2 4 5］ ［1 2 -1 4 5］ 最后遍历，第三个位置(下标为2) 本来应放3，但此时是-1，所以返回3，答案就是3。

 ?class?Solution: ????def?firstMissingPositive(self,?nums:?List[int])?->?int: ????????n=len(nums) ????????res_list=[-1]?*?n ????????#?print(res_list) ????????for?i?in?range(n): ?????????#??要判断这个数是否可以被交换 ????????????if?nums[i]?>=1?and?nums[i]<=n: ????????????????res_list[nums[i]-1]?=nums[i] ????????#?print(res_list) ????????for?i?in?range(n): ????????????if?res_list[i]?!=?i+1: ????????????????return?i+1 ????????return?n+1  

之前的系列文章点击阅读原文，以前文章发的很多都整理了，微信公众号不支持修改文章，所以公众号无法整理专辑。

专栏链接：https://blog.csdn.net/weixin_44510615/article/details/106162925

查看更多关于六十五、Leetcode数组系列（上篇）的详细内容...