算法设计大赛T13 - T14

算法设计大赛T13 - T14

T13 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

思路：
这题对python还是蛮简单的，求m*n的矩阵中是否存在元素target，可以将矩阵由二维降至一维的向量，在直接使用 in判断是否target存在，代码如下：

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        matrix = sum(matrix,[])
        return target in matrix

运行结果：

T14 给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

这道题目需要分为两步，第一是求数组中频数最大的元素，第二是在多组出现频数相同的元素中找到长度最短的。
第一步，寻找出现频数最大的元素：
在这一步中，我们可以通过遍历数组，求出每一个元素出现频数，储存为[出现频数，元素]的形式，再通过sort排序取出出现次数最多的元素
第二步，找出最短长度：
长度res 等于该元素最后出现的位置索引减去最先出现的位置索引，python中index方法可以求出该元素在列表中最先出现的位置，我们可以利用此特性，分别对列表以及列表的逆序进行 *** 作，求出所有出现频数最多元素的长度，其中最小的便是我们要求的结果，代码如下：

class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        du = []
        n = set(nums)
        cnt = 0
        for i in n:
            du.append([nums.count(i),i])
        du.sort(reverse = True)
        res = []
        for i in du:
            if i[0] == du[0][0]:
                res.append(len(nums) - nums.index(i[1]) - nums[::-1].index(i[1]))
        return min(res)

运行结果：