数据结构-3-排序、二分查找

排序

排序算法实现

实现归并排序、快速排序、插入排序、冒泡排序、选择排序、堆排序
代码见排序算法总结

编程实现 O(n) 时间复杂度内找到一组数据的第 K 大元素

def quicksort(num ,low ,high):  #快速排序
    if low< high:
        location = partition(num, low, high)
        quicksort(num, low, location - 1)
        quicksort(num, location + 1, high)
 
def partition(num, low, high):
    pivot = num[low]
    while (low < high):
        while (low < high and num[high] > pivot):
            high -= 1
        while (low < high and num[low] < pivot):
            low += 1
        temp = num[low]
        num[low] = num[high]
        num[high] = temp
    num[low] = pivot
    return low
 
def findkth(num,low,high,k):   #找到数组里第k个数
        index=partition(num,low,high)
        if index==k:return num[index]
        if index<k:
            return findkth(num,index+1,high,k)
        else:
            return findkth(num,low,index-1,k)
 
 
pai = [2,3,1,5,4,6]
# quicksort(pai, 0, len(pai) - 1)
 
print(findkth(pai,0,len(pai)-1,0))

leetcode-239-返回滑动窗口中的最大值

涉及队列

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        d = collections.deque()
        out = []
        for i, n in enumerate(nums):
            while d and nums[d[-1]] < n:
                d.pop()
            d += i,
            if d[0] == i - k:
                d.popleft()
            if i >= k - 1:
                out += nums[d[0]],
        return out

二分查找

实现一个有序数组的二分查找算法

需注意边界，参考：二分查找学习札记 (写的很详细)

代码如下

# coding: utf-8

def binary_search(sort_list, e):
    print(sort_list)
    left = 0
    right = len(sort_list) - 1
    while left <= right:
        mid = (left + right) // 2
        if sort_list[mid] < e:
            left = mid + 1
        elif sort_list[mid] > e:
            right = mid - 1
        else:
            return mid
    return -1

print(binary_search([1, 3, 4, 9, 10], 3))  # 1
print(binary_search([1, 3, 4, 9, 10], 0))  # -1
print(binary_search([], 0))  # -1

实现模糊二分查找算法（比如大于等于给定值的第一个元素）

代码如下

def binary_search(sort_list, target):
    left = 0
    right = len(sort_list) - 1
    while left <= right:
        mid = (left + right) // 2
        if sort_list[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    if left > len(sort_list) - 1:  # 如果数组中所有元素都小于target，left会越界
        return -1
    return left


print(binary_search([1, 3, 4, 9, 10], 3))  # 1
print(binary_search([1, 3, 3, 4, 9, 10], 3))  # 1
print(binary_search([1, 3, 4, 9, 10], 5))  # 3
print(binary_search([1, 3, 4, 9, 10], 10))  # 4
print(binary_search([1, 3, 4, 9, 10], 11))  # -1
print(binary_search([], 0))  # -1

二分查找变种

模式

如下：

def binary_search(sort_list, target):
    left = 0
    right = len(sort_list) - 1
    while left <= right:  # 如果取值范围是[left,right]，这里必须是 <=
        mid = (left + right) // 2
        if sort_list[mid] ？？？ target:  # <？  <=？
            left = mid + 1
        else:
            right = mid - 1
    return ？？？  # 返回left？ right？

确定return

因为最后跳出while (left <= right)循环条件是right < left，且right = left - 1。最后right和left一定是卡在”边界值”的左右两边，如果是比较值为key，查找大于等于（或者是大于）key的元素，则边界值就是等于key的所有元素的最右边那个，其实应该返回left

确定比较符号

查找大于等于key的元素，则知道应该使用判断符号<

参考

• 二分查找的变种
• 【二分查找】原型和变种以及相关思考

对应的 LeetCode 练习题

leetcode-69-Sqrt(x) （x 的平方根）

英文版：https://leetcode.com/problems/sqrtx/

中文版：https://leetcode-cn.com/problems/sqrtx/

方法一

# coding: utf-8

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        left = 0  # 非负数，范围[0,x]
        right = x
        while left <= right:
            mid = (left + right) // 2  # 使用其他语言时，为避免溢出可以写为  mid = left + (right - left) // 2
            # print(mid)
            if mid ** 2 > x:  # 使用其他语言时，为避免溢出可用除法代替乘法，写为 if mid > x // mid:  下同：if mid + 1 > x // (mid + 1)
                right = mid - 1
            else:
                if (mid + 1) ** 2 > x:  # 在这里判断某些情况可减少循环次数，如x=4
                    return mid
                left = mid + 1
        return right

s = Solution()
print(s.mySqrt(12))  # 3
print(s.mySqrt(8))  # 2
print(s.mySqrt(4))  # 2

方法二

这种写法更简洁，参考：3-4 short lines, Integer Newton, Every Language

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        r = x
        while r ** 2 > x:
            r = (r + x // r) // 2
        return r