4. Median of Two Sorted Arrays
We can use the method that find the k-th samallest element in two sorted list to solve this problem.
In this question, if the total length of this two list is odd, then the median will be the k-th smallest element (len(nums1)+len(nums2))/2
if the total length is even, then the median will be
(l/2-th element + l/2-1-th element)/2
思路就是转换成求两个有序序列中的第k小元素。
如果总长度为偶数，就是求第总长度/2 小的数
如果总长度为奇数，就是求
（第总长度/2 + 第总长度/2 -1）/2
求第K小元素时，
if not n1: return n2[k] if not n2: return n1[k]
先找出两个有序序列的第l/2小的元素，即他们的中位数，将l1 + l2和k比较，如果大于等于k, 就在前半部分找。再继续判断median1和median2的大小，如果m1>m2，我们就舍弃m1的后半段
return self.kthsmall(n1[:l1], n2, k)
否则就舍弃n2的后半段，注意这里K不变，因为舍弃的长度在K之外。
如果l1+l2小于K的话，我们就在后半段找，需要舍弃前边段。
如果m1>m2: return self.kthsmall(n1, n2[l2+1:], k-l2-1)
否则：return self.kthsmall(n1[l1+1:], n2, k-l1-1 )
注意这里要对k进行更新，因为舍弃的长度也包含在k里
33. Search in Rotated Sorted Array
截图来源：code ganker博客
Paste_Image.png
时间复杂度为O(logn)
81. Search in Rotated Sorted Array II
截图来源：code ganker博客
Paste_Image.png
与上一题不同的地方在于这里允许出现重复数字，对边缘进行移动，值到相遇或者边缘的值与mid值不相等：
while left<mid and nums[left]==nums[mid]: left += 1
时间复杂度在最坏情况下变为O(n)
34. Search for a Range
- 循环条件为
while left <= right:, 要包含等于，因为可能存在数组里只有1到2个数字这种情况 - 当找到target后，即
nums[mid] == target:此时将mid赋值给两个新的指针，lpivot, rpivot，从mid出发分别朝左右前进，如果
lpivot >0 and nums[lpivot] == target
rpivot < len(nums) and nums[rpivot] == target
就继续向左右移动这两个指针，最后返回[lpivot, rpivot]
35. Search Insert Position
循环条件中依然包含等于，原因和上一道题一样。
最后如果target不存在，返回r+1就可以了
50. Pow(x, n)
计算x的n次方。
分几种情况：n==0, n==1, n<0, n%2==0
当n<0时，if n<0: n = -n, x = 1/x，对n, x做相应的变化
if n%2 == 0: return self.myPow(x*x, n/2)
else: return x*self.myPow(x*x, n/2)
因为每次n都变为原来的二分之一，所以总运行时间为O(logn)
69. Sqrt(x)
对x进行二分法，l, r = 0, x
从x的一半开始试：
while l<= r:
mid = (l+r)/2
if mid*mid <= x < (mid+1)*(mid+1):
return mid
elif mid*mid > x:
r = mid -1
else:
l = mid +1
if mid*mid <= x < (mid+1)*(mid+1): 这句判断的原因是，x有可能不能恰好被开平方，比如10，sqrt(10) = 3
74. Search a 2D Matrix
在一个有序的二维矩阵中找target, 因为这个二维矩阵是有序的，我们依然可以按照最普通的二分查找来做。
m, n = len(matrix), len(matrix[0])
l, r = 0, m*n-1
while l <= r
mid = (l+r)/2
num = matrix[mid/n][mid%n]
if num == target:
return True
最重要的地方就是如何只根据mid来找到在二维数组中对应的数字。 num = matrix[mid/n][mid%n], n是每一行的元素个数，mid除n可以得到所在的行数，对n取余可以得到所在的列数。
*** if not matrix or target is None: return False
这里不能写matrix is None, 当matrix为[ ]时，就不属于None
153. Find Minimum in Rotated Sorted Array
依然是在rotated array中找值，这次没有给target, 而是让找出最小值，在没有旋转之前，最小值就是第一个值，因为是有序序列。
- O(n)解法：用for循环遍历数组，找到第一个
nums[i] > nums[i+1]时，返回nums[i+1]， 若都不存在，则返回nums[0]，此时证明序列是有序的并且没有被旋转。 - O(logn)解法：用二分查找来做。
while left <= right:
if nums[left] < nums[right]:
return nums[left]
else:
mid = (left + right)/2
if nums[mid] < nums[right]:
right = mid
else:
left = mid + 1
return nums[right]
和其他地方不同的地方在于，这里更新right时不要对mid减1，因为nums[mid]可能就是那个最小的数。如果对right进行mid-1，就会把最小的数给错过。循环终止后返回nums[right]
162. Find Peak Element
peak element就是比左右邻居都大的数，这题默认nums[-1]=nums[n]= 负无穷，题目要求复杂度为log形式，所以依然要用二分法来做。
while left < right:
mid = (left+right)/2
if nums[mid] > nums[mid+1]:
right = mid
else:
left = mid+1
return left
比较nums[mid]和nums[mid+1]，如果nums[mid]更大，就对right进行更新，将mid赋值给他。这里不需要mid-1, 因为mid这个元素，可能就是我们要找的peak元素，如果使right = mid-1，就有可能把这个元素给错过去。而left=mid+1是因为nums[mid+1]是那个更大的元素，将Left指向它，就不会错过。
*还有一点需要注意，循环条件不能有等于。有等于的话会循环超时。
*最后可以返回left也可以返回right，因为循环终止时，left=right
209. Minimum Size Subarray Sum
用Sliding window和two pointers可以得到O(n)解法：
left, right均从0开始，维护一个sliding window, 不断累加sum, 当sum>=s时，更新minlen, 并且减去nums[left]，将left向右移动一位，直到sum小于s。然后向右移动一位right，直到right到达数组边界为止。
注意right<len(nums), 是没有等于的，因为要累加nums[right]的值，有等于的话就会数组越界。
left, right, sum, minlen = 0, 0, 0, len(nums)+1
while right < len(nums):
sum += nums[right]
while sum >= s:
minlen = min(minlen, right - left +1)
sum -= nums[left]
left += 1
right += 1
if len(minlen)==len(nums)+1:
return 0
else:
return minlen
网友评论