导言

笔者最近在找实习，面试了一部分公司，靠着吃老本和刷几道 LeetCode 题目，在面试中苟延残喘，最痛苦的还是在线手撕代码，那个刺激劲仍历历在目。

在面试过程中，发现经常问到或者手撕的类型有：查找算法、排序算法（复杂度、稳定性等）、树（前中后遍历：递归和非递归实现）

在面试的时候，有些面试官会使劲给你提示，其实想表达一个信号，你第一时间没想到方案没事，如果能够在面试官的提示下把问题给解决了，那么你的能力应该也不差。

个人有几点体会：

  • 表达的时候逻辑一定要清晰
  • 第一次想到的方案不一定要是最优的，起码可以告诉面试官，我能够第一时间想到方案
  • 在进行算法优化的时候，面试官可能会提醒你（复杂度怎么优化，所以要记住一些常见复杂度的顺序和算法）兴许可以从中找到突破口

给自己总结一个初始模板吧，以后慢慢优化

我第一个想到的方案是 xx 算法，该算法的复杂度是 xx，思路是 xxx 我还有一个复杂度更低的算法 xxx，思路是 xxx

无他，多刷题吧～

今天就来看一道有关查找类型的题目

二分查找

适合场景

  • 二分查找依赖的是顺序表结构，简单点说就是数组
  • 二分查找针对的是有序数据。
  • 数据量太小不适合二分查找。
  • 数据量太大也不适合二分查找。

写二分算法的注意点

  • 循环退出条件
  • mid 的取值（防止溢出）
  • low 和 high 的更新

常规二分法

  • 循环写法
  1. from typing import List
  2. # 循环写法
  3. def binary_search(nums: List[int], target: int) -> int:
  4.     """
  5.     nums:一个数字列表
  6.     target：目标值
  7.     return：目标值在列表中的索引，
  8.     """
  9.     if len(nums) == 0:
  10.         return -1
  11.     low = 0
  12.     high = len(nums)-1 
  13.     while low<=high: # 小于等于
  14.         mid = low + ((high-low) >> 1) # 取整，移位更高效，防止溢出
  15.         if nums[mid] == target:
  16.             return mid
  17.         elif nums[mid] > target:
  18.             high = mid-1 # 
  19.         elif nums[mid] < target:
  20.             low = mid+1 # 
  21.     return -1
  • 递归写法
  1. from typing import List
  2. # 递归写法
  3. def binary_search(nums: List[int],low: int, high: int, target: int) -> int:
  4.     if low > high:
  5.         return -1
  6.     mid = low + ((high-low) >> 1) # 取整，移位更高效，防止溢出
  7.     if nums[mid] == target:
  8.         return mid
  9.     elif nums[mid] > target:
  10.         return binary_search(nums, low, mid-1, target)
  11.     elif nums[mid] < target:
  12.         return binary_search(nums, mid+1, high, target)

二分查找的变形

二分查找的变形有很多，常见的二分查找变形问题有

无他、刷题而已 - 图1

进阶题目

我们来看一道中等难度的二分查找相关的问题

LeetCode：540. 有序数组中的单一元素

问题

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。 示例 1: 输入: [1,1,2,3,3,4,4,8,8] 输出: 2 示例 2: 输入: [3,3,7,7,10,11,11] 输出: 10 注意: 您的方案应该在 O (log n) 时间复杂度和 O (1) 空间复杂度中运行。

解法

对于这道题，首先可以想到位运算的方法，但是该方法是 O(n) 复杂度

位运算解法

如果这道题没有要求是在 O(log n ) 复杂度下，那么可以使用位运算

  • 异或运算满足交换律
  • 相同的数异或为 0
  • 0 与一个数异或是本身
  1. class Solution:
  2.     def singleNonDuplicate(self, nums: List[int]) -> int:
  3.         temp = nums[0]
  4.         for i in nums[1:]:
  5.             temp ^= i
  6.         return temp

二分查找

关键词：有序

那如何判断我们想要的结果在二分之后的哪一部分呢？

一次面试时面试官提醒我说，为什么每个题目会给出示例呢，一般示例是很足够代表性的，不是随随便便选取的。

那我们就用示例来分析一下：
下表第一行是编号

  • 找到第一次二分的中点，mid = (0+8)/2 = 4，就是 3
  • 此时判断该值与前面的值是否相同，如果相同，我们计算一下 mid 之后的数组长度，如果是偶数，那么我们要找的值肯定在 mid-1 之前，反之。
  • 如果 mid 的值与后面的值相同呢？那我们就计算 mid+1 之后的数组长度，如果是偶数，那么我们要找到的值在 mid 之前。
  • 总之，我们以 mid 之后的数组长度的奇偶情况（如果mid的值与 mid-1 的值相同）或者 mid+1之后的数组长度的奇偶情况（如果mid的值与 mid-1 的值相同）

无他、刷题而已 - 图2

以下两种写法是一样的，只不过是在 while 里面判断 low==high 的情况还是在 while 外面判断

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        length = len(nums)
        low = 0
        high = length-1
        while low < high:
            mid = low+(high-low)//2
            flag = (high - mid)%2 == 0 # 判断 mid 之后的数组长度
            if nums[mid] == nums[mid-1]: # mid和前面的值相同 
                if flag: # mid 之后的数组长度是偶数
                    high = mid - 2
                else: # 
                    low = mid + 1
            elif nums[mid] == nums[mid+1]:  # mid 后面值的相同 
                if flag: # 偶数，但实际上是奇数，往后找我们要的数
                    low = mid + 2
                else:
                 high = mid - 1
            else:
                return nums[mid]
        return nums[low]

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        length = len(nums)
        low = 0
        high = length-1
        while low <= high:
            if low == high:
                return nums[high]
            mid = low+(high-low)//2
            flag = (high - mid)%2 == 0 # 判断 mid 之后的数组长度
            if nums[mid] == nums[mid-1]: # mid和前面的值相同 
                if flag: # mid 之后的数组长度是偶数
                    high = mid - 2
                else: # 
                    low = mid + 1
            elif nums[mid] == nums[mid+1]:  # mid 后面值的相同 
                if flag: # 偶数，但实际上是奇数，往后找我们要的数
                    low = mid + 2
                else:
                    high = mid - 1
            else:
                return nums[mid]

如何学习数据结构与算法

推荐极客时间的这门课程，可以巩固一下知识。
a48467ba12381a7929128852f34b465.jpg