本文共 2065 字，大约阅读时间需要 6 分钟。

查找排序习题

数据结构已经介绍完了，我很庆幸自己坚持下来了！之前有位读者给我留言，印象很深刻，他说:"放弃不难，但坚持一定很酷！"所以，，坚持下去吧！

1. 题目1:

给定两个字符串s和t，判断t是否为s重新排列后组成的单词

'''TOPIC: 查找排序习题1author: Bluetime: 2020-08-08QQ: 2458682080'''def isAnagram(s, t):    """    :param s: str    :param t: str    :return: bool    """        # 法一: 先排序，后比较  选择排序，时间复杂度O(nlogn)    # ss = list(s)    # tt = list(t)    # ss.sort()    # tt.sort()    # return ss == tt    # 法二: 先排序，后比较    # return sorted(list(s)) == sorted(list(t))    # 法三: 用字典保存两个字符串里字母出现的数量  时间复杂度O(n)    dict1 = {
   }    dict2 = {
   }    for ch in s:        # 如果ch在键里，则+1，如果不在键里，则获取ch为键，并数量+1        dict1[ch] = dict1.get(ch, 0) + 1  # 如果不存在，则返回0再加1，    for ch in t:        dict2[ch] = dict2.get(ch, 0) + 1    return dict2 == dict1s = 'blue't1 = 'lube't2 = 'bull'print(isAnagram(s, t1))print(isAnagram(s, t2))# 方法介绍: # dict.get(key, default=None)# key -- 字典中要查找的键。# default -- 如果指定键的值不存在时，返回该默认值。# 返回值： 返回指定键的值，如果键不在字典中返回默认值 None 或者设置的默认值。

结果为:

TrueFalse

2. 题目2

给定一个m*n的二维列表，查找一个数是否存在，列表有以下特性:

1. 每一行的列表从左到右已经排好序
2. 每一行第一个数比上一行最后一个数大，即列表本身有序
   例如:
   [
   [1, 3, 5, 7],
   [10, 11, 13, 15],
   [18, 21, 23, 25]
   ]

代码:

def searchMatrix(matrix, target):    """    :param matrix: list[list[int]]    :param target: int    :return: bool    """        # 法一:线性查找    时间复杂度0(mn)    # for line in matrix:    #     if target in line:    #         return True    # return False    # 法二: 二分查找 时间复杂度O(logn)    h = len(matrix)     # 长    if h == 0:        return False    w = len(matrix[0])  # 宽    if w == 0:        return False    left = 0    right = w * h - 1  # 列表整体长度为 w * h    while left <= right:   # 候选区有值        mid = (left + right) // 2        # 获取二维列表中数值的下标        i = mid // w        j = mid % w        if matrix[i][j] == target:            return True        elif matrix[i][j] > target:            right = mid - 1        else:            left = mid + 1    else:        return Falsem = [    [1, 3, 5, 7],    [10, 11, 13, 15],    [18, 21, 23, 25]]print(searchMatrix(m, 13))

结果为:True

转载地址：http://kdiwi.baihongyu.com/