力扣面试经典150 —— 1-5题

• 力扣面试经典150题
• 在 VScode 中安装 LeetCode 插件即可使用 VScode 刷题，安装 Debug LeetCode 插件可以免费 debug
• 本文使用 python 语言解题，文中 “数组” 通常指 python 列表；文中 “指针” 通常指 python 列表索引

---

1. [简单] 合并两个有序数组

• 题目链接
• 标签：数组、双指针、排序
  

1.1 解法1：双指针

• 由于两个数组都已经有序，使用双指针分别遍历两个数组，每次将较小的元素加入结果数组。考虑到两个数组长度可能不一样，可以考察已经遍历的数组长度，只从未遍历完成的数组中取元素；也可以将已遍历完成数组中取的值设为 inf。下面给出后者代码

  class Solution:
      def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
          """
          Do not return anything, modify nums1 in-place instead.
          """
          res = []
          pos1 = pos2 = 0
          while len(res) < m + n:
          	# 已遍历完成的数组，取出的元素值设为无限大
              num1 = float('inf') if pos1 >= m else nums1[pos1]
              num2 = float('inf') if pos2 >= n else nums2[pos2]
              if num1 < num2:
                  res.append(num1)
                  pos1 += 1
              else:
                  res.append(num2)
                  pos2 += 1
          # 原地修改 nums1 的内容
          nums1[:] = res
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19

• 空间复杂度均为 $O(m+n)$，前者时间复杂度 $O(m+n)$，后者时间复杂度 $O(2\max (m,n))$

1.2 解法2：逆向双指针

• 解法1中使用辅助数组 res 增加了空间复杂度，由于题目中 nums1 尾部有空余空间，可以直接从两个数组元素的尾部开始反向遍历，总是把较大元素覆盖到 nums1 尾部。注意到当从 nums1 本身复制一个元素到最后占据一个空位时，nums1 前面又出现一个空位，因此 nums1 中永远有足够的空间容纳 nums2 的全部元素

  def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
          """
          Do not return anything, modify nums1 in-place instead.
          """
          pos1 = m - 1
          pos2 = n - 1
          tail = -1
          while pos1 >= 0 or pos2 >= 0:
              if pos1 == -1:
                  nums1[tail] = nums2[pos2]
                  pos2 -= 1
              elif pos2 == -1:
                  nums1[tail] = nums1[pos1]
                  pos1 -= 1
              elif nums1[pos1] > nums2[pos2]:
                  nums1[tail] = nums1[pos1]
                  pos1 -= 1
              else:
                  nums1[tail] = nums2[pos2]
                  pos2 -= 1
              tail -= 1
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21

• 时间复杂度 $O(m+n)$，空间复杂度 $O(1)$

2. [简单] 移除元素

• 题目链接
• 难度：简单
• 标签：数组、双指针
  

2.1 解法1：双指针

• 左右两个指针都初始化指向 0 索引位置，右指针遍历数组 nums，将不等于 val 的元素复制到左指针位置，并把左指针右移一格，当右指针遍历完成时，左指针索引位置即为新长度

  class Solution:
      def removeElement(self, nums: List[int], val: int) -> int:
          left = 0
          for right in range(len(nums)):
              if nums[right] != val:
                  nums[left] = nums[right]
                  left += 1
          return left
  1
  2
  3
  4
  5
  6
  7
  8

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$

3. [简单] 删除有序数组中的重复项

• 题目链接
• 难度：简单
• 标签：数组、双指针
  

3.1 解法1：双指针

• 左右两个指针都初始化指向 1 索引位置，由于数组 nums 有序，只需右指针遍历 nums，将 nums[right] != nums[right-1] 的元素复制到左指针位置，并把左指针右移一格，当右指针遍历完成时，左指针索引位置即为新长度。和上一题很类似

  class Solution:
      def removeDuplicates(self, nums: List[int]) -> int:
          left = 1
          for right in range(1, len(nums)):
              if nums[right] != nums[right-1]:
                  nums[left] = nums[right]
                  left += 1
          return left
  1
  2
  3
  4
  5
  6
  7
  8

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$

4. [中等] 删除有序数组中的重复项 II

• 题目链接
• 标签：数组、双指针
  

4.1 解法1：双指针+计数

• 和上一题思路一致，但是增加一个计算器以允许保留一个重复元素

  class Solution:
      def removeDuplicates(self, nums: List[int]) -> int:
          left, cnt = 1, 1
          for right in range(1, len(nums)):
              if nums[right] != nums[right-1]:
              	# 元素值变化，重置计数器
                  nums[left] = nums[right]
                  left += 1
                  cnt = 1
              else:
              	# 元素值不变，计数器加1
                  cnt += 1
                  if cnt <= 2:
                  	# 允许保留一个重复元素
                      nums[left] = nums[right]
                      left += 1
          return left
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$

4.2 解法2：双指针

• 由于给定数组 nums 是有序的，所以相同元素必然连续。左右两个指针都初始化指向 2 索引位置，右指针遍历 nums，如果 nums[right] == nums[left-2] 意味着必有 nums[right] == nums[left-1] == nums[left-2]，这时已经有两个相同值元素，右指针指示的元素应该舍去。因此，只需将 nums[right] != nums[left-2] 的元素复制到左指针位置，并把左指针右移一格。当右指针遍历完成时，左指针索引位置即为新长度

  class Solution:
      def removeDuplicates(self, nums: List[int]) -> int:
          left, right = 2, 2
          for right in range(2, len(nums)):
              if nums[right] != nums[left-2]:
                  nums[left] = nums[right]
                  left += 1
          return left
  1
  2
  3
  4
  5
  6
  7
  8

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$

5. [简单] 多数元素

• 题目链接
• 标签：数组、哈希表、分治、计数、排序
  

5.1 解法1：哈希表

• 用哈希表记录数组中每个元素出现的次数，该哈希表的每个键值对中，键代表一个元素，值代表元素出现次数。在计数过程中，可以实时检查各个元素当前出现次数，并在找到满足条件的值时直接返回

  def majorityElement(self, nums: List[int]) -> int:
          cnts = {}
          limit = len(nums) // 2
          for num in nums:
              if num not in cnts:
                  cnts[num] = 1
              else:
                  cnts[num] += 1
                  if cnts[num] > limit:
                      break
          return num
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11

• 时间复杂度 $O(n)$，空间复杂度 $O(n)$

5.2 解法2：排序

• 利用众数的性质，当数组元素单调递增排序时，索引为 $\lfloor \frac{n}{2}\rfloor$ 的元素一定是众数

  def majorityElement(self, nums: List[int]) -> int:
      nums.sort()
      return nums[len(nums) // 2]
  1
  2
  3

• 时间复杂度和空间复杂度取决于排序算法

5.3 解法3：分治

• 设 a 是数组的众数，那么将数组分成两部分时，a 必定是至少一部分的众数。这个结论可以用反证法证明，若数组众数 a 既不是左半边的众数也不是右半边的众数，那么它本身没法成为整个数组的众数。
• 因此可以用分治法解决这个问题：将数组分成左右两部分，分别求出左半部分的众数 a1 以及右半部分的众数 a2，随后在 a1 和 a2 中选出正确的众数。递归边界是子数组长度为 1 的情况，这时数组元素就是众数

  def majorityElement(self, nums: List[int]) -> int:
      def _rec(lo, hi):
          # 递归边界：长度为1的列表中众数就是元素本身
          if lo == hi:
              return nums[lo]
          
          # 分治递归计算左右两部分的众数
          mid = (hi - lo) // 2 + lo
          left = _rec(lo, mid)
          right = _rec(mid + 1, hi)
  
          # 左右众数相等，则本段众数也一致
          if left == right:
              return left
  
          # 左右众数不等，则本段众数为出现更多的那个
          left_count = sum(1 for i in range(lo, hi + 1) if nums[i] == left)
          right_count = sum(1 for i in range(lo, hi + 1) if nums[i] == right)
          return left if left_count > right_count else right
          
      return _rec(0, len(nums)-1)
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21

• 时间复杂度 $O(n\log n)$，空间复杂度 $O(\log n)$

  

5.4 解法4：Boyer-Moore 投票算法

• 之前的方法都没法实现 $O(n)$ 的时间复制度和 $O(1)$ 的空间复杂度，为了实现这个要求，必须在常数次遍历过程中确定众数，并且不设置任何额外空间。一个巧妙的想法是，把数组元素想象成消消乐游戏，不同的元素就消除掉，这样最后剩下的就一定是众数
• 为了在遍历过程中进行消除，可以在遍历过程中设置候选众数，并对其出现次数进行计数，如果遇到候选众数则计数加一，遇到其他数则计数减一（理解为消除了一对不同的元素），当计数减到0时，则设置新遇到的元素为新的候选众数。一个示例如下

  原始数组:   [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
  候选众数:  	7  7  7  7  7  7   5  5   5  5  5  5   7  7  7  7
  众数计数:    1  2  1  2  1  0   1  0   1  2  1  0   1  2  3  4
  1
  2
  3

  如此遍历之后，最后的候选众数就是真实众数

  def majorityElement(self, nums: List[int]) -> int:
          candidate = nums[0]
          cnt = 0
  
          for num in nums:
              if cnt == 0:
                  candidate = num    
              cnt = cnt + 1 if num == candidate else cnt - 1
  
          return candidate
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$