数据结构总结
数组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