Leetcode查找(Python和java实现)

1. 搜索范围 【Search for a Range】

• 给定一个排序的整数数组，找出给定目标值的开始和结束位置。
• 你的算法的运行时间复杂度必须是O(logn)的数量级。
• 如果在数组中没有找到目标值，返回[-1, -1]。
• 例如，给定[5, 7, 7, 8, 8, 10]和目标值8，返回[3, 4] 。

分析：已经排好序了，用二分查找最为合适

Python

def search_range(arr, low, high, key):
    out = [-1, -1]
    mid = (low+high) // 2
    
    if low == high & key != arr[low]:
        return [-1, -1]
	
	if key == arr[mid]:
        for i in range(mid, high):  # range()左闭右开
            if key == arr[i]:
                out[1] = i
        j = mid
       
        while arr[j] == key:
        	out[0] = j
            j = j - 1
        
        return out
    elif key < arr[mid]:
        temp_high = mid
        return search_range(arr, low=low, high=temp_high, key=key)
    else:
        temp_low = mid + 1
        return search_range(arr, low=temp_low, high=high, key=key)


if __name__ == '__main__':
    list1 = [5, 7, 7, 8, 8, 10, 10]
    print(search_range(list1, low=0, high=len(list1), key=10))
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

2. 搜索插入位置【Search Insert Position】

给定一个排序的数组和一个目标值，如果找到了目标，则返回索引。如果没有，则返回索引 如果按顺序插入，则返回其所在的索引。你可以假设数组中没有重复的东西。

Python

方法一：循环遍历，这里不再赘述。
方法二：先排序，然后返回插入的值的 index

def searchInsert(nums, target):
    if target not in nums:
        nums.append(target) # 末尾追加
        nums.sort()  # 排序
    return nums.index(target)  # 返回索引
1
2
3
4
5

方法三：二叉搜索(推荐)

def search_insert(nums, low, high, key):

    if low == high:
        return low

    mid = (high + low) // 2

    if nums[mid] < key:
        temp_low = mid + 1
        return search_insert(nums, low=temp_low, high=high, key=key)
    elif nums[mid] > key:
        temp_high = mid
        return search_insert(nums, low=low, high=temp_high, key=key)
    else:  # nums[mid] == key
        return mid


if __name__ == '__main__':
    list1 = [1, 3, 5, 7, 8, 10]
    print(search_insert(list1, low=0, high=len(list1), key=9))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3. 搜索一个二维矩阵【Search a 2D Matrix】

写一个有效的算法，在一个m×n的矩阵中搜索一个值。这个矩阵有以下特性。

• 每行的整数从左到右排序。
• 每一行的第一个整数大于前一行的最后一个整数。

例如，以下矩阵。

[[1,3,5,7],
 [10,11,16,20],
 [23,30,34,50]]
1
2
3

Python

解法一：使用numpy将二维数组变为一维数组，然后使用二叉搜索

def search_2dm(matrix_flatten, low, high, target):

    if low >= high and matrix_flatten[low] != target:   # 没有key值
        return False

    mid = (high + low) // 2

    if matrix_flatten[mid] > target:
        temp_high = mid
        return search_2dm(matrix_flatten, low=low, high=temp_high, target=target)
    elif matrix_flatten[mid] < target:
        temp_low = mid + 1
        return search_2dm(matrix_flatten, low=temp_low, high=high, target=target)

    else:  # matrix_flatten[mid] == key
        return True


if __name__ == '__main__':
    list1 = [[1, 3, 5, 7],
             [10, 11, 16, 20],
             [23, 30, 34, 50]]
    list1 = np.array(list1).flatten()
    print(search_2dm(list1, low=0, high=len(list1), target=2))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

方法二：

def search_matrix(matrix, target):
        matrix = np.array(matrix)

        row = matrix.shape[0]  # 获取行号
        column = matrix.shape[1]  # 获取列数

        first = 0
        last = row * column

        while first < last:
            mid = first + (last-first)//2
            value = matrix[(mid // column), (mid % column)]

            if value == target:
                return True
            elif value < target:
                first = mid + 1
            else:
                last = mid
        return False


if __name__ == '__main__':
    list1 = [[1, 3, 5, 7],
             [10, 11, 16, 20],
             [23, 30, 34, 50]]

    print(search_matrix(list1, 70))
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