力扣面试经典150 —

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

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

文章目录

1. [简单] 合并两个有序数组
- 1.1 解法1：双指针
- 1.2 解法2：逆向双指针
2. [简单] 移除元素
- 2.1 解法1：双指针
3. [简单] 删除有序数组中的重复项
- 3.1 解法1：双指针
4. [中等] 删除有序数组中的重复项 II
- 4.1 解法1：双指针+计数
- 4.2 解法2：双指针
5. [简单] 多数元素
- 5.1 解法1：哈希表
- 5.2 解法2：排序
- 5.3 解法3：分治
- 5.4 解法4：Boyer-Moore 投票算法

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

空间复杂度均为 $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

时间复杂度 $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

时间复杂度 $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

时间复杂度 $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

时间复杂度 $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
```
时间复杂度 $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

时间复杂度 $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]
```
时间复杂度和空间复杂度取决于排序算法

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)

时间复杂度 $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

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

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