数据结构总结

数组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数组相关题目

485. 最大连续 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