[数据结构与算法]三、Leetbook数组

一、数组简介

一） 集合、列表和数组

https://leetcode-cn.com/leetbook/read/array-and-string/ybfut/

集合：①元素类型不一定相同 ②元素没有顺序
列表：①元素具有顺序 ②长度可变 ③常见表现形式：数组、链表 ④元素类型不一定相同
数组：①是列表的表现形式之一 ②具有索引（不同：普通列表没有索引）③元素在内存中连续存储，每个元素占有相同大小的内存（区别于链表） ④ c++和Java的数组元素类型一致，python可以不一致

二）数组的操作

https://leetcode-cn.com/leetbook/read/array-and-string/yjcir/

读取

对于数组，计算机会记下索引为0的内存地址。找到索引为0的元素的内存地址（2008），然后将地址加上目标索引值（2008+2）得到目标地址（2010），获得对应的目标元素。

• 时间复杂度O(1)

查找元素

从开头逐步往后查找，查到就停止。

• 时间复杂度O(N)

插入元素

从数组末尾插入，或插入到别的位置-先腾出空间-再插入。（用链表插入更快）

删除元素

删除某元素后，会留下空缺，之后的元素对该位置进行填补。

• 时间复杂度O(N)

三）习题

1. 寻找数组的中心索引

https://leetcode-cn.com/leetbook/read/array-and-string/yf47s/

1. 思路：创建两个list，一个存入每个从开头的数的累加，一个存入从最后的数的累加、且每次insert到改list开头，则维护完后，若两list的第i位数相等，则该点为pivot。

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        
        frontSum = []
        behindSum = []
        n = len(nums)
        self.fTemp = 0
        self.bTemp = 0

        for i in range(n):
            self.fTemp += nums[i]
            frontSum.append(self.fTemp)
            self.bTemp += nums[n-1-i]
            behindSum.insert(0, self.bTemp)
        
        for i in range(n):
            if frontSum[i] == behindSum[i]:
                return i
        
        return -1

2) 改进
思路2：建立两个动态的变量：数前之和，数后之和。数前之和–每次加上nums[i]前一个数，数后之和-总sum每次减去nums[i]。当两数相等，i即为pivot。

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        sum = 0
        
        for i in range(len(nums)):
            sum += nums[i]
        
        frontTemp = 0
        behindTemp = sum

        for i in range(len(nums)):
            if i > 0:
                frontTemp+=nums[i-1]
            behindTemp -= nums[i]
            #print("i: %d ft: %d bt: %d"%(i,frontTemp,behindTemp))

            if frontTemp == behindTemp:
                return i

        return -1

2. 搜索插入位置

https://leetcode-cn.com/leetbook/read/array-and-string/cxqdh/
题目要求时间复杂度O(logn))，可使用二分查找

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1

        while left <= right:
            mid = (left + right)//2
            if nums[mid]==target:
                return mid
            elif nums[mid]>target:
                right = mid - 1
            else:
                left = mid + 1
        return left

用二分法，结果一定能找到：
1.当target存在时：
① mid在两数中间，直接找到；
② 若left和right相邻（即left+1 = right），则：
1）若target是left：mid=(left+right)//2=>mid = left，所以nums[mid]=target，找到
2） 若target是right：mid=(left+right)//2=>mid=left，而nums[mid]<target，所以新left = mid+1=right=>新mid= (新left+right)//2=right，所以nums[mid]=target，找到

2.当target不存在时：
假设已到最后一步，right<left，则target在right和left之间，而left是最接近target且比target大的值（https://leetcode-cn.com/leetbook/read/array-and-string/cxqdh/?discussion=jnXJqG），因此返回left

3. 合并区间

https://leetcode-cn.com/leetbook/read/array-and-string/c5tv3/
思路：比较两区间首末，除了不重叠的区间，其他都进行融合。

算法误区：对融合后的区间，如何和剩下的区间进行比对，顺序性和重复性没有解决。因此没有全部融合。
错误：

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        n = len(intervals)
        i = 0
        while i < (len(intervals)-1):
            start_1 = intervals[i][0]
            end_1 = intervals[i][1]
            j = i + 1
            while j < len(intervals):
                start_2 = intervals[j][0]
                end_2 = intervals[j][1]

                if not ((end_1<start_2) or (start_1>end_2)):         
                    intervals[i][0] = min(start_1,start_2)
                    intervals[i][1] = max(end_1, end_2)
                    start_1 = intervals[i][0]
                    end_1 = intervals[i][1]
                    del intervals[j]
                else:
                    j +=1
            i += 1
        return intervals

重写算法：
将原区间集用sort进行排序，则区间元素会以开头数字来升序排列。然后建立结果list，对比之后区间元素的开头与list中元素结尾的大小，来确定是否对list中最后一个元素融合；若不需，则直接加入结果list。

正确：

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        theList = []
        theList.append(intervals[0])
        for interv in intervals[1:]:
            if interv[0]<= theList[-1][-1]:
                end = max(theList[-1][-1],interv[1])
                theList[-1][-1] = end
            else:
                theList.append(interv)
        return theList

二、二维数组

一） 二维数组简介

常用来处理矩阵问题。计算机申请一段连续空间，并记录数组[0][0]位置的内存地址

二）习题

1. 旋转矩阵

https://leetcode-cn.com/leetbook/read/array-and-string/clpgd/
思路：
如果是顺时针旋转90°
一定是先对角线翻转，再水平翻转
如果是逆时针旋转90°
一定是先水平翻转，再对角线翻转
https://leetcode-cn.com/leetbook/read/array-and-string/clpgd/?discussion=56LF2O

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # to obatain a 90 degree clockwise, rotate matrix, first diagonal flip, then mirror flip
        # diagonal flip
        for i in range(len(matrix)):
             for j in range(0, i+1):
                 matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        
        
        # mirror flip
        for i in range(len(matrix)):
            for j in range(len(matrix[0])//2):
                matrix[i][j], matrix[i][len(matrix)-1-j] = matrix[i][len(matrix)-1-j], matrix[i][j]

将最后一行改为

matrix[i][:] = matrix[i][::-1]

更容易理解，但时间会更久一点

方法3：

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        matrix[:]=zip(*matrix[::-1])

zip(a,b)可对a,b两个list纵向相叠，返回元组。
zip(* matrix)可对matrix元素纵向相叠，即转置（对角线翻转）。其中，星号使矩阵像list一样纵向相叠，而视矩阵为单一的list。
顺时针旋转90°： matrix[:]=zip(*matrix[::-1])
逆时针旋转90°：

2. 零矩阵

https://leetcode-cn.com/leetbook/read/array-and-string/clpgd/
方法4最好。

思路1：遍历矩阵，记录有0的row，有0的列；然后遍历每一行，对有0行全置为0，对每一行遍历每一列，对有0列的位置置为0

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        rowZero = set()
        colZero = set()
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    rowZero.add(i)
                    colZero.add(j)
        
        rowIndex = 0
        while rowIndex < len(matrix):
            if rowIndex in rowZero:
                matrix[rowIndex] = [0]*len(matrix[0])
            colIndex = 0
            while colIndex< len(matrix[0]):
                if colIndex in colZero:
                    matrix[rowIndex][colIndex]=0
                colIndex+=1
            rowIndex += 1

2)思路简化
记录有0的行数和列数后，遍历矩阵，当i存在于有0行的set中，或j存在，该位置置0

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        rowZero = set()
        colZero = set()
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    rowZero.add(i)
                    colZero.add(j)
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if (i in rowZero) or (j in colZero):
                    matrix[i][j] = 0

方法简单，但结果更慢了。

3）换数据类型
将set改为相应长度的list，对该换0的位置标记1。

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        rowZero = [0]*len(matrix)
        colZero = [0]*len(matrix[0])
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    rowZero[i] = 1
                    colZero[j] = 1
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if (rowZero[i] == 1) or (colZero[j] == 1):
                    matrix[i][j] = 0

结果差异不大。还是第一种方法快。
4)对第一种简化
将while+ij自增，改为for，来去掉两个index的内存消耗

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        rowZero = set()
        colZero = set()
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    rowZero.add(i)
                    colZero.add(j)        
       
        for rowIndex in range(len(matrix)):
            if rowIndex in rowZero:
                matrix[rowIndex] = [0]*len(matrix[0])
            for colIndex in range(len(matrix[0])):
                if colIndex in colZero:
                    matrix[rowIndex][colIndex]=0

结果：内存消耗大大减少，且一样快

总结：①用set，list记录差不多快 ②用for比while减少内存消耗

3. 对角线遍历

https://leetcode-cn.com/leetbook/read/array-and-string/cuxq3/
1）思路1：
通过对每条划线标序号，对应每条线经过的点，可找到一些规律。序号为n=len(mat)之前的每次对角线，若序号为偶数，经过的点为从(i,0),(i-1,1)…(0，i)；若序号为奇数，经过的点为（0,i）(1,i-1)…(i,0)。序号为n+1以及之后的每条对角线，row值为以n为镜面，对应序号对角线，各位置值加上距离n的gap。

缺点：
算法适合方阵（m=n），对非方阵矩阵不适用。

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        n = len(mat)
        # an iteration dict: store the position result of each iteration, use iteration index as the key
        itrDict = {} 
        
        for i in range(n):
            if i%2 == 0: 
                pos = []
                for colIndex in range(i+1):
                    pos.append((i-colIndex,colIndex))
                itrDict[i] = pos
            else:
                pos = []
                for rowIndex in range(i+1):
                    pos.append((rowIndex, i-rowIndex))
                itrDict[i] = pos
        
        for j in range(n,2*n-1):
            
            gap = j-(n-1)
            pos = []
            posTempt = itrDict[(n-1-gap)]
            for eachPos in posTempt:
                pos.append((eachPos[0]+gap,eachPos[1]+gap))
            itrDict[j] = pos
        
        
        #print(itrDict)

        resList = []
        for value in itrDict.values():
            for pos in value:
                resList.append(mat[pos[0]][pos[1]])
        
        #print(resList)
        return resList

2）思路2
对每条对角线的边界进行判断，到了边界，改变下一步位置，使其到达下一条对角线的起点。

待完成！！！！！！