前言

学习python数据结构与算法，学习常用的算法，

41.查找排序部分习题

选题部分来自

42.查找排序习题1

第一个思想是将两个字符串转换为列表排序，如果排完后相等，则True,否则False

在python的排序有两个方法，一个是list对象的sort方法，另外一个是builtin函数里面sorted，主要区别： 1.sort仅针对于list对象排序，无返回值, 会改变原来队列顺序 2.sorted是一个单独函数，可以对可迭代（iteration）对象排序，不局限于list，它不改变原生数据，重新生成一个新的队列。

第二个思想是将两个字符串中每个字符的个数存在字典里，比较字典是否相等， 时间复杂度为O(n),理论上比排序要快，排序O(nlogn)

43.查找排序习题2

第一种思路是线性查找，复杂度是O(n^2),因为 if in 是复杂度为n的查找 第二种思路是二分查找，复杂度是O(nlogn),因为题目中给了。里面每个列表是有序的，所以可以用二分查找，把二维矩阵看成是一维的，每行的第一个整数大于前一行的最后一个整数。 二分查找 中的中间值要改变，从一维转换成二维。 中讲过了二分查找 先找规律，3的位置是[0][3],4的位置是[1][0] 0 1 2 3 4 5 6 7 8 9 10 11

相当于 行的位置 i = num//4 列的位置 j = num%4 注意越界情况：矩阵为[] 或者[[],[],[],[]]的情况，使得right = -1

44.查找排序习题3

第一种思路是遍历，从前往后找，[2,7,11,15]，2和7比，2和11比，2和15比，7和11比，7和15比。。。找到相加等于目标值输出下标，因为从前往后找，i在前，j在后。

输入有序的数组，就可以用二分查找的方法写 不过这里超出时间限制，可能用时都比较少。

45.查找排序习题4

第二个思路是二分查找 先把这个列表的每一个元素及其下标存在一个新列表内，在新列表按元素大小排好序，再进行二分查找，在力扣里还是超出了时间限制。 在网上找到另外一种解法，很巧妙。 创建一个字典，如果目标元素和遍历的元素的差值不在该字典中，就将该遍历的元素存在字典里（键是元素，值是下标）， 如果差值在这个字典里，说明已经满足了有两个值加起来等于目标值， 于是返回这个差值的下标和该遍历元素的下标。因为是从左往右找，所以越往后找的下标一定在后面。

总结

练了下排序和查找的题