[数据结构]排序、二分查找

排序

练习:Sliding Window Maximum

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
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums:
return []

highest = max(nums[:k])
ans = [0]*(len(nums)-k+1)
ans[0] = highest
last = nums[0]

for i in range(1, len(nums)-k+1):
if highest == last:
highest = max(nums[i:i+k])
elif nums[i+k-1] >= highest:
highest = nums[i+k-1]

ans[i] = highest
last = nums[i]

return ans

二分查找

练习:Sqrt(x) (x 的平方根)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x == 0:
return 0
left = 1
right = x / 2 + 1

while left <= right:
mid = left + (right - left) / 2
sq = x / mid
if sq > mid:
left = mid + 1
elif sq < mid:
right = mid - 1
else:
return mid
return right

相关链接

编程计划的第3个任务
第三次任务 打卡表格