学习目标：

1.分享一下leetcode上查找排序相关的面试题

题目大纲：

1.给两个字符串s和t，判断t是否为s的重新排列后组成的单词
s = “anagram”, t = “nagaram”, return true.
s=“rat”,t=“car”, return false.
2.给定一个m*n的二维列表，查找一个数是否存在。列表有下列特性:
每一行的列表从左到右已经排序好。
每一行第一个数比上一行最后一个数大。
在这里插入图片描述
3.给定一个列表和一个整数，设计算法找到两个数的下标，
使得两个数之和为给定的整数。保证肯定仅有一个结果。
例如，列表[1,2,5,4]与目标整数3，1+2=3，结果为(0,1)。

题目一：

我们看到这个题型，你要知道的是写法有很多，那就是比看谁写的简洁和程序运行效率高了。

class Solution:
	def isAnagram(self, s, t):
		"""
		s: str t: str  r: bool
		"""
		ss = list(s)
		tt = list(t)
		ss.sort()
		tt.sort()
		return ss == tt

时间复杂度：排序中有sort，sort基于归并排序，它的时间复杂度为O(nlogn)。

甚至可以一步到位，sorted也是排序列表，只是新建一个列表在去存储，而不是向sort在原来的列表上存储。

class Solution:
	def isAnagram(self, s, t):
		return sorted(list(s)) == sorted(list(t))

但是我们要写出高效率的代码，就要从其他思想去思考，找到时间复杂度更低的算法。

class Solution:
	def isAnagram(self, s, t):
		dict1 = {}  # {'a':1, 'b':2}
		dict2 = {}
		for ch in s:
			dict1[ch] = dict1.get(ch, 0) + 1
			# dict.get 有则加1，无则新建一个
		for ch in t:
			dict2[ch] = dict2.get(ch, 0) + 1
		return dict1 == dict2

时间复杂度为:O(n)

题目二：

class Solution:
	def searchMatrix(self, matrix, target):
	"""
	martix: list[list[int]] target:int r:bool
	"""
		for line in matrix:
			if target in line:
				return True
		return False

时间复杂度：在列表中的in操作中，也是O(n),所以时间复杂度为O(n^2)。总体来说，还是很慢。

改进使用2分查找

class Solution:
	def searchMatrix(self, matrix, target):
		h = len(matrix)
		if h == 0:
			return False
		w = len(matrix[0])
		if w == 0:
			return False
		left = 0
		right = w * h -1
		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 False

时间复杂度为:O(logn) 此时代码的效率就已经非常高了。

题目三

先尝试用我们的常规思路去编写


class Solution:
	def twoSum(self, nums, target):
		n = len(nums)
		for i in range(n):
			for j in range(i+1,n):
				if nums[i] + num[j] == target:
					return sorted([i, j])

时间复杂度为:O(n^2)

我们可以改进，采取用二分查找，不过二分查找的前提是列表为有序，我们先假设列表有序时，我们该怎么去编写。

class Solution:
	def binary_search(self, li, left, right, val):
		while left <= right:
			mid = (left + right) // 2
			if li[mid] == val:
				return mid
			elif li[mid] > val:
				right = mid -1
			else:
				left = mid + 1
		else:
			return None
	
	def twoSum(self, nums, target):
		for i in range(len(nums)):
			a = nums[i]
			b = target -a
		# 我们采取这种方式时，可能找b的下标我们可以用index，但是index复杂度也是O(n),所以并不采取
			if b >= a:
				j = self.binary_search(nums, i+1, len(nums)-1, b)
			else:
				j = self.binary_search(nums, 0, i-1, b)	
			if j:
				break 
		return sorted[i, j])

现在我们对无序的列表进行排序，我们二分查找肯定是要用的，只不过我们要做的就是把无序转成有序，并且记住原来列表的各个值下标。

class Solution:
	def binary_search(self, li, left, right, val):
		while left <= right:
			mid = (left + right) // 2
			if li[mid] == val:
				return mid
			elif li[mid] > val:
				right = mid -1
			else:
				left = mid + 1
		else:
			return None
	
	def twoSum(self, nums, target):
		new_nums = [[num, i] for i, num in enumerate(nums)]
		# 新建一个二维列表
		new_nums.sort(key=lambda x:x[0])
		# 二维以num排序
		for i in range(len(new_nums)):
			a = nums[i][0]
			b = target -a
		# 我们采取这种方式时，可能找b的下标我们可以用index，但是index复杂度也是O(n),所以并不采取
			if b >= a:
				j = self.binary_search(new_nums, i+1, len(nums)-1, b)
			else:
				j = self.binary_search(new_nums, 0, i-1, b)	
			if j:
				break 
		return sorted[new_nums[i][1], new_nums[j][1])