查找习题
# 习题1
给两个字符串s和t, 判断t是否为s重新排序后组成的单词.
举个栗子:
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.
# -- 时间复杂度不可能比O(nlogn)快
def is_anagram_1(s, t):
return sorted(list(s)) == sorted(list(t))
# -- 时间复杂度O(n)
def is_anagram_2(s, t):
dict_1 = {}
dict_2 = {}
for ch in s:
dict_1[ch] = dict_1.get(ch, 0) + 1
for ch in t:
dict_2[ch] = dict_2.get(ch, 0) + 1
return dict_1 == dict_2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 习题2
给定一个m
*n的二维列表, 查找一个数是否存在.
列表有以下特性: eg [ [1,3,5,7], [10,11,16,20], [23,30,34,50] ]
每一行的列表从左到右已经排序好.
每一行第一个数比上一行最后一个数大.
使用二分法的思想会比第一种快!! O(logn) < O(n)
"""
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
"""
# -- 线性查找
# 假设该矩阵有m行n列,那么时间复杂度为O(mn),变相的可以看作是线性查找,即一个一个的查找.
def search_matrix_1(matrix, target):
for line in matrix: # O(m)
if target in line: # O(n)
return True
else:
return False
# -- 二分查找
# 因为矩阵是有序的,虽说是二维的,但依旧可以考虑用二分查找的思想来解决
# 时间复杂度. O(logn) n指二维列表元素的个数
def search_matrix_2(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
# -- mid=(left+right)//2. 不能直接定位到行下标和列下标,要加工一下
"""
0 1 2 3
4 5 6 7
8 9 10 11
所在位置的下标 除以4得到自己所在行;对4求余得到自己所在列
"""
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
return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# 习题3
给定一个列表和一个整数. 设计算法找到两个数的下标.使得两个数之和为给定的整数. <可以保证有结果且只有一个结果>.
举个栗子:
列表[1,2,5,4]与目标整数3, 1+2=3, 结果为 (0,1).
方式一: 会重复相加
def two_sum_1(li, target):
n = len(li)
# 这种算法不好,太慢,会重复相加 [3,2,4] 3+2 2+3
for i in range(n):
for j in range(n):
# i!=j 是为了避免 [3,2,4] 3+3=6的情况.
if i != j:
if li[i] + li[j] == target:
return sorted([i, j])
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
方式二: 相加次数与方法一相比,减少了一半
def two_sum_2(li, target):
n = len(li)
# [3,2,4] 3+2 3+4 2+4 每个数跟在后面的数相加(当然跟前面的也可以)
for i in range(n):
for j in range(i + 1, n):
if li[i] + li[j] == target:
return sorted([i, j])
1
2
3
4
5
6
7
2
3
4
5
6
7
方式三, 添加了一个条件,假设列表是有序的, 使用二分查找
eg: 在[2,6,7,8]找相加为14的两个数. 拿到6后,通过二分法在6位置后面的数[7,8]中找8
class Solution:
def binary_search(self, li, left, right, val):
# left = 0
# right = len(li) - 1
while left <= right:
mid = (left + right) // 2
if li[mid] == val:
return mid
elif li[mid] > val:
right = mid - 1
else:
left = mid + 1
return None
# 自己加了一个条件,若li列表是有序的.
def two_sum_3(self, li, target):
n = len(li)
for i in range(n):
a = li[i]
b = target - a
# self.binary_search(li[i + 1:], b) # 切片会消耗资源,传left和right进去更好
j = self.binary_search(li, i + 1, n - 1, b)
if j:
break
return i, j
## -- 列表是有序的,还可以这样做,依旧是二分查找的思想
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
left = 0
right = len(nums) - 1
while left < right:
if nums[left] + nums[right] == target:
return [left,right]
if nums[left] + nums[right] < target:
left += 1
if nums[left] + nums[right] > target:
right -= 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
方式四, 列表是无序的,使用二分查找.
class Solution:
def binary_search(self, li, left, right, val):
while left <= right:
mid = (left + right) // 2
if li[mid][0] == val:
return mid
elif li[mid][0] > val:
right = mid - 1
else:
left = mid + 1
return None
def twoSum(self, li, target):
new_nums = [[v, i] for i, v in enumerate(li)] # 记录下排序之前每个元素的下标
new_nums.sort(key=lambda x: x[0]) # sort原地改变,返回None;sorted不是原地变,返回改变后的列表
n = len(new_nums)
for i in range(n):
a = new_nums[i][0]
b = target - a
j = self.binary_search(new_nums, i + 1, n - 1, b)
if j:
break
return sorted([new_nums[i][1], new_nums[j][1]])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23