重中之重的二分查找
原创
数组
4. 寻找两个正序数组的中位数
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5Solution
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
if len(nums1) > len(nums2):
return self.findMedianSortedArrays(nums2, nums1)
infinty = 2**40
m, n = len(nums1), len(nums2)
left, right, ansi = 0, m, -1
# median1：前一部分的最大值
# median2：后一部分的最小值
median1, median2 = 0, 0
while left <= right:
# 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
# // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
i = (left + right) // 2
j = (m + n + 1) // 2 - i
# nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
nums_im1 = (-infinty if i == 0 else nums1[i - 1])
nums_i = (infinty if i == m else nums1[i])
nums_jm1 = (-infinty if j == 0 else nums2[j - 1])
nums_j = (infinty if j == n else nums2[j])
if nums_im1 <= nums_j:
ansi = i
median1, median2 = max(nums_im1, nums_jm1), min(nums_i, nums_j)
left = i + 1
else:
right = i - 1
return (median1 + median2) / 2 if (m + n) % 2 == 0 else median133. 搜索旋转排序数组
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1Solution
直接使用二分法，判断那个二分点,有几种可能性 1. 直接等于target 2. 在左半边的递增区域: a. target 在 left 和 mid 之间; b. 不在之间 3. 在右半边的递增区域: a. target 在 mid 和 right 之间; b. 不在之间
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums: return -1
left, right = 0, len(nums)-1
while left < right:
mid = (left+right)//2
if nums[mid] == target: return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid-1
else:
left = mid+1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid-1
return left if nums[left] == target else -1287. 寻找重复数
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Example 1:
Input: [1,3,4,2,2]
Output: 2Example 2:
Input: [3,1,3,4,2]
Output: 3Solution
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
di = {}
for i in range(len(nums)):
if nums[i] not in di:
di[nums[i]] = 1
else:
return nums[i]
return -134. 在排序数组中查找元素的第一和最后一位
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]Solution
class Solution:
def searchRange(self, nums, target: int):
# 取起始下标
l, r = 0, len(nums) - 1
while l < r:
mid = (l + r) // 2
if nums[mid] >= target:
r = mid
else:
l = mid + 1
# 没找到
if not nums or nums[l] != target:
return [-1,-1]
# 取结束下标
a, b = 0, len(nums) - 1
while a < b:
mid = (a + b + 1) // 2
if nums[mid] <= target:
a = mid
else:
b = mid - 1
return [l,a]矩阵
240. 搜索二维矩阵 II
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Example:
Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]Given target = 5, return true.
Given target = 20, return false.
Solution
从左下开始search
class Solution(object):
def searchMatrix(self, matrix, target):
if not matrix: return False
i = len(matrix)-1
j = 0
while i>=0 and j<=len(matrix[0])-1:
if matrix[i][j] > target: i-=1
elif matrix[i][j] < target: j+=1
elif matrix[i][j] == target: return True
return False378. 有序矩阵中第K小的元素
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
Example:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
return 13.Solution-heap
class Solution:
def kthSmallest(self, matrix, k: int) -> int:
import heapq
q = []
for r in matrix:
for e in r:
heapq.heappush(q,e)
for _ in range(k):
res = heapq.heappop(q)
return res
Solution-heap
klogk: 一次添加右和下，pop出其中较小的，每次pop k-1，pop k次返回
def kthSmallest_(self, matrix, k):
row, col = len(matrix), len(matrix[0])
h = [(matrix[0,0],0,0)]
res = 0
visited = set((0,0))
while k > 0:
res, r, c = h.pop()
if r+1 < row and (r+1,c) not in visited:
heapq.heappush(h, matrix[r+1][c], r+1, c)
visited.add((r+1, c))
if c+1 < col and (r,c+1) not in visited:
heapq.heappush(h, (matrix[r][c+1], r, c+1))
visited.add(r, c+1)
k -= 1
return res其他
378. 二叉搜索树中第K小的元素
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Example 1:
Input: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
Output: 1Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
Output: 3Solution
class TreeNode(object):
def __init__(x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def kthSmallest(self, root, k):
nums = []
def helper(root):
if not root: return
helper(root.left)
nums.append(root.val)
helper(root.right)
helper(root)
return nums[k-1] if k<=len(nums) else -169. Sqrt(x)
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4
Output: 2Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.Solution
class Solution:
def mySqrt(self, x: int) -> int:
l, r = 0, x
while l <= r:
mid = l + (r-l)//2
if mid * mid <= x < (mid+1)*(mid+1):
return mid
elif x < mid * mid:
r = mid
else:
l = mid + 1原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。