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

发表于
参加Datawhale的编程计划的第3个任务，涉及排序、二分查找，用python实现。。

排序

练习：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个任务
第三次任务 打卡表格