数据结构01——数组
2021/7/10 23:38:23
本文主要是介绍数据结构01——数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
数据结构总结
数组Array:连续存储的一系列相同类型的数据
其中访问(按照索引访问)、搜索(直接搜索元素)、插入、删除的时间复杂度分别为O(1),O(N),O(N),O(N),适合读多写少的情况
01数组的基本操作
#创建数组 a = [] #添加数组 #添加到尾部 a.append(1) a.append(2) a.append(3) #插入元素 a.insert(1,4) #修改元素 a[3] = 0 #删除元素 #按照元素删除 a.remove(0) #按照索引 a.pop(0) #遍历数组 #方法一: for i in a: print(i) #方法二: for i,element in enumerate(a): print(i,element) #方法三: for i in range(len(a)): print(i, a[i]) #查找元素 #查找元素的位置 print(a.index(4)) #数组排序默认升序 a.sort() a.sort(reverse = True)
02数组相关题目
- 最大连续 1 的个数
#原本的思路建立两个新的数组存放每一段连续1的个数最后找到最大值 #缺点:时间复杂度O(N)和空间复杂度O(N)都比较高 # 没有考虑到原本数组长度为0的情况 class Solution: def findMaxConsecutiveOnes(self, nums: List[int]) -> int: alist = [] munber = [] for i in range(len(nums)): if nums[i] == 0: alist.append(i) if len(alist) == 1: if len(nums)-alist[-1]-1 > alist[0]: return (len(nums)-alist[-1]-1) else: return alist[0] elif len(alist)>1: for j in range(1,len(alist)): munber.append(alist[j]-alist[j-1]-1) max_n = max(munber) if max_n >= alist[0]: if len(nums)-alist[-1]-1 > max_n: return (len(nums)-alist[-1]-1) else: return max_n else: return alist[0] else: return len(nums)
#思路二: 先判断数组长度,若为0直接返回0 加入计数变量和不存储每一段的结果,直接进行比较大小 时间复杂度O(N)空间复杂度O(1) class Solution: def findMaxConsecutiveOnes(self, nums: List[int]) -> int: if len(nums) == 0: return 0 result = 0 count = 0 for i in range(len(nums)): if nums[i]!=0: count +=1 else: result = max(result,count) count = 0 return max(result,count)
283.给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
#原本思路,用冒泡排序的方法 时间复杂度O(N²)空间复杂度O(1) class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) for j in range(0,n-1): count = 0 for i in range(0,n-1-j): if nums[i] == 0: nums[i],nums[i+1] = nums[i+1],nums[i] count +=1 if count == 0: break
#思路2 将不为0的数字按顺序向前移动,后面补0 #时间复杂度O(N),空间复杂度O(1) class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ index = 0 for i in range(len(nums)): if nums[i]!=0: nums[index]=nums[i] index +=1 for j in range(index,len(nums)): nums[j] = 0
27,移除元素
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
#双指针————左指针扫描不是VAL的元素,右指针扫描是Val的元素,然后交换两个的值,左右指针相等的时候,判断指针的值是否等于Val #时间复杂度 O(N) class Solution: def removeElement(self, nums: List[int], val: int) -> int: if len(nums) == 0: return 0 #双指针算法 left = 0 right = len(nums)-1 while left<right: while left<right and nums[left]!=val: #小于的条件不能少,是停止循环的条件 left += 1 while left<right and nums[right] == val: right -= 1 nums[left],nums[right] = nums[right],nums[left] if nums[left] == val: return left else: return left+1
这篇关于数据结构01——数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-26Adobe国际认证(证书)认证价值详解
- 2024-07-2501.计算机组成原理和结构
- 2024-07-25城域网
- 2024-07-25为什么API经济在经济不确定时期表现突出
- 2024-07-24Python实现Java mybatis-plus 产生的SQL自动化测试SQL速度和判断SQL是否走索引
- 2024-07-24轻松获取天气信息:免费天气API一览
- 2024-07-24深入理解 Java17 新特性:Sealed Classes
- 2024-07-24大厂的第三方支付业务架构设计
- 2024-07-23docker及tomcat 部署java项目
- 2024-07-23Adobe国际认证详解-艺术设计专业的就业前景