chapter2_array_matrix_algorithm

chapter2_array_matrix_algorithm

矩阵类算法

[TOC]

1. 把数组中的 0 移到末尾

def moveZeroes():
    #遍历，数组，前面记住不为0的值，往依次迁移，遍历完数组，除记录不为0的数，直接填充为0
    nums = [ 0, 1, 0, 3, 12 ]
    vn = 0
    for i,v in enumerate(nums):
        if v != 0:
            nums[vn] = v
            vn += 1
    nums[vn:] = [0]*(len(nums)-vn)
    print(nums)
moveZeroes()

2. 改变矩阵维度

import numpy as np
def matrixReshape(r,c):
    #先判断，改变数组是否符合要求.创建需要改变的数组,
    # 通过数组之间行与列的关系，直接遍历数组进行填充。
    nums =[ [ 1, 2 ],[ 3, 4 ] ]
    r1, c1 = len(nums), len(nums[0])

    assert (r != r1 or c != c1)
    M_r2 = [[ 0 for j in range(c)] for i in range(r)]

    index = 0
    for i in range(r1):
        for j in range(c1):
            r2, c2 = index // c,  index % c
            M_r2[r2][c2] = nums[i][j]
            index += 1
    print(M_r2)

    M_r1 = np.array(nums).reshape(r,c)
    print(M_r1)
matrixReshape(1,4)

3. 找出数组中最长的连续

def findMaxConsecutiveOnes():
    #遍历数组，每次记录连续1的长度，到转折的时候，求最大即可
    nums = [0,0,0,1,1,0,1,1,1]
    maxc,temp = 0,0
    for i,v in  enumerate(nums):
        if v == 1:
            temp += 1
        else:
            maxc = max(temp,maxc)
            temp = 0
    print(temp)
    return temp
findMaxConsecutiveOnes()

4. 搜索二维矩阵 II

def searchMatrix():
    #由于行和列都是有顺序的，所以直接通过使用一次为规律去判断就行，
    # 时间复杂度为O(pow((m**2+n**2),1/2))
    # matrix = [
    #     [ 1, 5, 9 ],
    #     [ 10, 11, 13 ],
    #     [ 12, 13, 15 ]
    # ]
    matrix =[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
    target = 20
    #起始值从(0,0)开始
    def sm():
        for m in matrix:
           if target in m:
               return True
        return False

    #起始值从(0,n)开始,从此开始会比从(0,0)开始快
    def sm1():
        if matrix == None or len(matrix) == 0 or len(matrix[0]) == 0: return False
        i, j, m, n = 0, len(matrix[0])-1, len(matrix), len(matrix[ 0 ])-1
        while (i < m and j >= 0):
            if matrix[ i ][ j ] == target: return True
            if target <= matrix[ i  ][ j ] : j -= 1
            else: i += 1
        return False

    res = sm()
    print(res)
    res = sm1()
    print(res)
searchMatrix()

5. 有序矩阵的 Kth Element

def kthSmallest():
    # 由于是有序数组，每一个矩阵块（当前矩阵的子矩阵）最后一列都是当前行最大值，
    # 利用二分查找的思想，通过到达中值的次数为指标，进行分离左右查找，当找到计数为k，即为第k个数
    matrix = [[1,2],[1,3]]
    def ks(matrix,k):
        k -= 1
        lv, rv, m, n = matrix[0][0], matrix[-1][-1], len(matrix), len(matrix[ 0 ])
        while(lv <= rv):
            mid, cnt = lv + (rv - lv)//2, 0
            i, j = 0, n-1
            while(i < m and j >= 0):
                if matrix[i][j] <= mid:
                    cnt += (j + 1)
                    i += 1
                else:
                    j -= 1

            if (k < cnt):
                rv = mid - 1
            else:
                lv = mid + 1
        print(lv)
        return lv

    ks(matrix,3)
kthSmallest()

6. 一个数组元素在 [1, n] 之间，其中一个数被替换为另一个数，找出重复的数和丢失的数

def findErrorNums():
    #由于是[1,n]的数，且只重复一次，所以直接通过数学公式就可以算出
    nums = [2,3,2]
    r = sum(nums) - sum(set(nums))
    r1 = sum(range(1, len(nums) + 1)) - sum(set(nums))
    print([r,r1])
findErrorNums()

7. 找出数组中重复的数，数组值在 [1, n] 之间

def findDuplicate():
    # 由于是[1, n] 之间，所以值v<len(nums),因此，利用二分查找，遍历数组，记录小于mid值的个数cnt，
    # 如果cnt > mid 说明小于mid中的数值，是有重复的，反之大于等于mid的数是有重复的。
    nums = [ 3, 1, 3, 4, 2 ]
    def fd1():
        l, r = 1, len(nums) - 1
        while (l <= r):
            mid = l + (r - l) // 2
            cnt = 0
            for i in range(len(nums)):
                if nums[ i ] <= mid:
                    cnt += 1
            if cnt > mid:
                r = mid - 1
            else:
                l = mid + 1
        print(l)
        return l

    #因为只有一个值是重复的，所以直接可以算出来
    def fd2():
        return  (sum(nums) - sum(set(nums))) // (len(nums) - len(set(nums)))

    #双指针解法，类似于有环链表中找出环的入口：
    def fd3():
        if len(nums) > 1:
            slow = nums[ 0 ]
            fast = nums[ nums[ 0 ] ]
            while slow != fast:
                slow = nums[ slow ]
                fast = nums[ nums[ fast ] ]
            print(slow, fast)
            entry = 0
            while entry != slow:
                entry = nums[ entry ]
                slow = nums[ slow ]
            print(slow, entry)
            return entry

    fd1()
    fd2()
    fd3()
findDuplicate()

8. 数组相邻差值的个数

def constructArray():
    # 先弄k个间隔数据，再弄n-k的数组，由于间隔相差值问题，通过观察，数值奇偶部分，
    # 相差数值是低高规律分布，因此流程如下：
    n = 10; k = 5
    data = [1 for i in range(n)]

    intervel = k
    for i in range(1,k+1):
       print(i)
       if i % 2 == 1:
           data[i] = data[i-1] + intervel
       else:
           data[i] = data[i-1] - intervel
       intervel -= 1
    print(data)
    if k + 1 <= n:
        for i in range(k+1,n):
            data[i] = i+1
    print(data)
    return data
constructArray()

9. 数组的度

def findShortestSubArray():
    #使用map数据结果 ，记录数据的第一个index和最后一个index 然后求出最大频率的值，输出长度即可
    #方法1
    nums = [ 1, 1 ]

    def fssa1():
        from collections import Counter
        v = Counter(nums)
        maxv = Counter(nums).most_common(1)[ 0 ][ 1 ]
        print(maxv)
        k = [ k for k, v in v.items() if v == maxv ]
        print(k)
        res = 1e100
        for c in k:
            x, y = 0, 0
            cc = maxv
            for i, v in enumerate(nums):
                if v == c and cc >= 1:
                    cc -= 1
                if v == c and cc == maxv - 1: x = i
                if v == c and cc == 0: y = i
            res = min(res, y - x + 1)

        print(res)
        return res

    #方法2
    def fssa2():
        left, right, count = {}, {}, {}
        for i, x in enumerate(nums):
            if x not in left: left[ x ] = i
            right[ x ] = i
            count[ x ] = count.get(x, 0) + 1

        ans = len(nums)
        degree = max(count.values())
        for x in count:
            if count[ x ] == degree:
                ans = min(ans, right[ x ] - left[ x ] + 1)

        return ans

    fssa1()
    fssa2()
findShortestSubArray()

10. 对角元素相等的矩阵

def isToeplitzMatrix():
    # 遍历行row和列col，通过分别+1,到达下个数，判断是否相等。如果相等，继续判断，
    # 如果不相等，就返回False结束，遍历完返回True
    
    matrix = [
        [ 1, 2, 3, 4 ],
        [ 5, 1, 2, 3 ],
        [ 9, 2, 1, 2 ]
    ]

    def itm():
        m, n = len(matrix), len(matrix[ 0 ])
        def check(mv, matrix, i, j, m, n ):
            if (i >= m or j >= n):
                return True

            if (mv != matrix[ i ][j]):
                return False
            b = check(mv, matrix, i + 1, j + 1, m, n)
            return b

        for i in range(m):
            if not check(matrix[i][0],matrix, i, 0, m, n):
                return False

        for i in range(n):
            if not check(matrix[ 0 ][ i ], matrix, 0, i, m, n):
                return False
        return True

    print(itm())
isToeplitzMatrix()

11. 分隔数组

def arrayNesting():
    # 题目描述：S[i] 表示一个集合，集合的第一个元素是 A[i]，第二个元素是 A[A[i]]，如此嵌套下去。求最大的 S[i]。
    # 此题就如同一个链表，只是有v-index-v-index：值-索引之间转化进行连接。我们做的就是找到出现相同索引的时候就停止，
    # 这时就是一个区间，就如果链表中的一个环。而要找到一个最大的最环，在不同的起点，会出现不同的环。
    # 要做的是，遍历过的环，就不在遍历，并且记录遍历过环的最大长度即可
    nums = [0,2,1]
    maxv = 0
    for i, a in enumerate(nums):

        cnt = 0
        j = i
        while(nums[j] != -1):
           cnt += 1
           t = nums[j]
           nums[j] = -1
           j = t
        l = set(nums)
        if l == {-1} and l.__sizeof__() == 1 :
            break
        print(l)
        maxv = max(maxv,cnt)
    print(maxv)
    return maxv
arrayNesting()

12. 嵌套数组

def maxChunksToSorted():
    # 题目描述：分隔数组，使得对每部分排序后数组就为有序。
    # 解题思路，我们通过观察，从左一直遍历到右，已当前值为后面最小值为划分区间就能够划分，
    # 比如index=0开始，index=1 v=0是后面[2:]区间的组最小值，即划分一个区间，
    # 类比 2,3,4分别是后面的最小值，所以划分的区间是4。
    # 因此，可以整理思路，如果前面区间的最大值等于index，就可以划分区间。原因。数据是属于[1,...,n]的
    arr =[1,0,2,3,4]
    maxv,res_c = 0, 0
    for i, v in enumerate(arr):
        maxv = max(maxv,v)
        if maxv == i:
            res_c += 1
    print(res_c)
    return res_c
maxChunksToSorted()