leetcode hot100：一、解题思路大全：技巧（只出现一次的数字、多数元素、颜色分类、下一个排列、寻找重复数）、矩阵（矩阵置零、螺旋矩阵、旋转图像、搜索二维矩阵Ⅱ）

因为某大厂的算法没有撕出来，怒而整理该贴。部分题目有AC代码。

技巧

只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

1 <= nums.length <= 3 * 10^4
-3 * 10^4 <= nums[i] <= 3 * 10^4
除了某个元素只出现一次以外，其余每个元素均出现两次。

思路

我们可以利用 异或运算（XOR） 的特性：

异或的性质：
a ^ a = 0（相同数字异或结果为 0）
a ^ 0 = a（任何数字与 0 异或仍是它本身）
异或满足交换律和结合律，即 a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b。

因此，对整个数组进行异或运算，最终结果就是只出现一次的数字。

代码

class Solution: def singleNumber(self, nums: List[int]) -> int: res = 0 for num in nums: res ^= num return res

多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

n == nums.length
1 <= n <= 5 * 10^4
-10^9 <= nums[i] <= 10^9

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

思路1：排序

假设整个数组元素个数为n，因为多数元素的个数一定大于n//2。
所以排序后，下标为n//2的元素一定是多数元素。
因为假设排序后的数组构成如下：

前x个比多数元素小的元素+k个多数元素+后y个比多数元素大的元素其中x一定小于n//2，y一定小于n//2，不然就和多数元素的定义违背了所以构成就是x+k+y=n其中x<n//2，yn//2画线段长度，找到中间的点，那么一定是在k那部分出现的。

代码复杂度为O(nlogn)，因为python底层的nums.sort()时间复杂度是这个。
空间复杂度为O(1)（原地排序）或O(n)（非原地排序）。

代码1：排序

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

0ms，击败100.00%

思路2：候选人算法

维护一个候选人数字和候选人数字对应的选票，然后遍历数组。
如果遍历的当前数字和候选人数字不同的话，候选人数字对应的选票-1.
如果遍历的当前数字和候选人数字相同的话，候选人数字对应的选票+1.
如果选票为0，候选人数字被替代成当前数字。

这个算法正确是因为多数元素的选票最后一定>=0，所以最后候选人数字一定是多数数字。时间复杂度为O(n)，空间复杂度为O(2)

代码2：候选人算法

class Solution: def majorityElement(self, nums: List[int]) -> int: candidate = nums[0] vote = 1 for i in range(1, len(nums)): if candidate != nums[i]: vote -= 1 else: vote += 1 if vote == 0: candidate = nums[i] vote = 1 return candidate

6ms，击败54.58%。
明明时间复杂度更低，但是实际运行时间更长hhh

颜色分类

思路：荷兰国旗解法/三指针法/三分类问题

荷兰国旗问题就是该题目的问题。
三指针法适用于该类的所有变种，就是需要划分为三个部分
＜x和＝x和＞x的三个部分的问题。

我们维护三个指针：

• left：0的右边界（指向最终数组最后一个0的下标+1）
• right：2的左边界（指向最终数组第一个2的下标-1）
• cur：当前遍历的数字。

初始时left为0，cur为0，right为len(nums)-1，然后随着cur的向右遍历，
left逐步向右扩大，right逐步向左扩大，直到我们cur超过right指针，表示所有的0和2都已经排序好，那么相应地，1也会排序好。

注意：当nums[right]==2时，我们不应该有cur+=1。
即right和cur位置进行交换，因为right位置的数字可能是0，1，2。
所以cur不能向右移动，因为需要二次检查。
而如果nums[cur]==0，那么就是left和cur位置进行交换。
又因为left永远指向第一个非0位置，并且left永远在cur的左边。
所以left位置都是排列好的数字，所以left位置只会是1.所以不需要二次检查。
可以通过[1,2,0]例子来查看。

代码

class Solution: def sortColors(self, nums: List[int]) -> None: \"\"\" Do not return anything, modify nums in-place instead. \"\"\" left, cur = 0, 0 right = len(nums)-1 while cur <= right: if nums[cur] == 0 : nums[left], nums[cur] = nums[cur], nums[left] left += 1 cur += 1 elif nums[cur] == 2: nums[right], nums[cur] = nums[cur], nums[right] right -= 1 \"\"\" 注意这里不能有cur += 1。right和cur位置进行交换，因为right位置的数字可能是0，1，2 所以cur不能向右移动，因为需要二次检查。而如果nums[cur]==0，那么就是left和cur位置进行交换 又因为left永远指向第一个非0位置+left永远在cur的左边，所以left位置都是排列好的数字 所以left位置只会是1.所以不需要二次检查。可以通过[1,2,0]例子来查看。 \"\"\" else: cur += 1 return 

0ms，击败100.00%

下一个排列

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

提示：
1 <= nums.length <= 100
0 <= nums[i] <= 100

思路

错误思路

最开始我想的思路是：

从左到右遍历数组，对每个数找到其右边第一个大于它的数。 - 找得到，冒泡到当前数的前面，并进行输出 - 找不到，继续向右遍历下一个数 如果直到遍历完所有数，都找不到，则直接输出升序排列的数组。为此我们可以预处理整个数组，得到rightMax，如果rightMax都是-1，则意味着直到遍历完所有的数，都会找不到右边更大的数，那么直接输出升序排列的数组。

但实际上这样的思路是错的，归根结底错在从左到右遍历这上面。
因为越左的数权重越大，越右的数权重越小，我们要找的下一个更大的字典序排列应该是尽可能修改越右的数的。

其次，错误的点在于，不应该找右边第一个大于它的数。而应该找右边第一个大于它且最接近它的数。

譬如对于例子1,3,2，按照我的思路一开始修改的是
3,1,2，但实际上对于这个例子的正确答案应该是2,1,3。

正确思路

1. 边界处理：
   若数组长度为 1，直接返回。
2. 寻找关键位置 i：
   从右向左扫描，找到第一个位置 i，使得 nums[i] < nums[i+1]。
   → 这个 i 是最右侧的、可以通过交换让排列变大的位置。
   若未找到（即整个数组降序），说明当前为最大排列，直接反转数组得到最小排列。
3. 寻找交换元素 j：
   从右向左扫描，找到第一个位置 j，使得 nums[j] > nums[i]。
   → 这个 j 对应的元素是右侧比 nums[i] 大的最小元素，交换后能保证增幅最小。
4. 交换 i 和 j：
   交换后，排列在位置 i 处被增大，右侧仍保持降序。
5. 反转右侧元素：
   将 i+1 到末尾的元素反转，使其变为升序。
   → 由于右侧原本降序，反转后变为最小排列，确保整体为下一个最小的字典序排列。

代码

class Solution: def nextPermutation(self, nums: List[int]) -> None: \"\"\" Do not return anything, modify nums in-place instead. \"\"\" if len(nums)==1: return # 从右往左找到第一个可以被增大的位置，即我们希望找到一个位置 i，使得右侧存在比 nums[i] 更大的元素 i = len(nums) - 2 while i >= 0 and nums[i] >= nums[i + 1]: i -= 1 if i<0: nums.sort() return # 对这个位置i，寻找右侧第一个比它大的元素，下标为j。一定存在这么一个j，因为我们找到了这么一个i j = len(nums)-1 while j >= 0 and nums[j] <= nums[i]: j -= 1 # 交换i和j所在的元素 nums[i], nums[j] = nums[j], nums[i] # 交换后，反转 i 右侧的元素，确保这部分是最小排列。 nums[i+1:] = nums[i+1:][::-1] return 

寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

提示：

• 1 <= n <= 10^5
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

进阶：

• 如何证明 nums 中至少存在一个重复的数字?
• 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

思路

最关键点在于1 <= nums[i] <= n，所以将数组视为一个链表，其中 nums[i] 表示节点 i 指向的下一个节点是 nums[i]。由于存在重复数字，链表一定存在环，且环的入口就是重复的数字。
确定这个链表不会存在独立节点的关键点就是因为数字范围是 [1, n]，而数组长度是 n + 1，因此可以将 nums[i] 看作指针。
那么就转换为了快慢指针问题。

1. 第一阶段：检测环：
   用快慢指针，慢指针每次走一步（slow = nums[slow]），快指针每次走两步（fast = nums[nums[fast]]）。直到快慢指针相遇。
2. 第二阶段：找到环的入口（重复数字）：
   将快指针重置到起点（0），然后快慢指针每次都走一步。
   再次相遇的点就是环的入口（重复数字）。

矩阵

矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

提示：

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -2^31 <= matrix[i][j] <= 2^31 - 1

进阶：

一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？

思路

一开始想的是多起点bfs，但是这样的话空间复杂度最坏是O（m*n），而且bfs也会让同一行或者同一列被多次访问，性能不算很高。

所以想的是，用第一行来记录哪些列需要被置零，第一列来记录哪些行需要被置零，并且用两个变量来记录本来第一行是否就存在0，第一列是否就存在0，这样的话空间复杂度为O（1）

代码

class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: \"\"\" Do not return anything, modify matrix in-place instead. \"\"\" m, n = len(matrix), len(matrix[0]) firstRowHasZero = any(matrix[0][j] == 0 for j in range(n)) firstColHasZero = any(matrix[i][0] == 0 for i in range(m)) # 标记需要置零的行和列 for i in range(1, m): for j in range(1, n): if matrix[i][j] == 0:  matrix[i][0] = 0  matrix[0][j] = 0 # 根据标记置零 for i in range(1, m): for j in range(1, n): if matrix[i][0] == 0 or matrix[0][j] == 0:  matrix[i][j] = 0 # 处理第一行和第一列 if firstRowHasZero: for j in range(n): matrix[0][j] = 0 if firstColHasZero: for i in range(m): matrix[i][0] = 0 return matrix # 返回修改后的矩阵 

螺旋矩阵

又是一道做过的笔试题

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

思路

没什么好说的，这个就是一个模拟。

代码

DIRS = (0, 1), (1, 0), (0, -1), (-1, 0) # 右下左上class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: m, n = len(matrix), len(matrix[0]) ans = [] i = j = di = 0 for _ in range(m * n): # 一共走 mn 步 ans.append(matrix[i][j]) matrix[i][j] = None # 标记，表示已经访问过（已经加入答案） x, y = i + DIRS[di][0], j + DIRS[di][1] # 下一步的位置 # 如果 (x, y) 出界或者已经访问过 if x < 0 or x >= m or y < 0 or y >= n or matrix[x][y] is None: di = (di + 1) % 4 # 右转 90° i += DIRS[di][0] j += DIRS[di][1] # 走一步 return ans

旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

提示：

• n = matrix.length = matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

思路

又是一道做过的笔试题

矩阵顺时针旋转 90º 后，可找到以下规律：

「第 i 行」元素旋转到「第 n−1−i 列」元素；
「第 j 列」元素旋转到「第 j 行」元素；

根据以上「元素旋转公式」，考虑遍历矩阵，将各元素依次写入到旋转后的索引位置。但仍存在问题：在写入一个元素 matrix[i][j]→matrix[j][n−1−i] 后，原矩阵元素 matrix[j][n−1−i] 就会被覆盖（即丢失），而此丢失的元素就无法被写入到旋转后的索引位置了。

为解决此问题，考虑借助一个「辅助矩阵」暂存原矩阵，通过遍历辅助矩阵所有元素，将各元素填入「原矩阵」旋转后的新索引位置即可。

代码

class Solution: def rotate(self, matrix: List[List[int]]) -> None: n = len(matrix) # 深拷贝 matrix -> tmp tmp = copy.deepcopy(matrix) # 根据元素旋转公式，遍历修改原矩阵 matrix 的各元素 for i in range(n): for j in range(n): matrix[j][n - 1 - i] = tmp[i][j]

搜索二维矩阵Ⅱ

又是一道做过的笔试题

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -10^9 <= matrix[i][j] <= 10^9
• -10^9 <= target <= 10^9

思路

因为m和n不大，才百级，所以要么暴力，要么遍历行，然后每行二分

代码

class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: m = len(matrix) n = len(matrix[0]) # 遍历每行，对行使用二分 for i in range(m): # 要确保该行的第一个数字小于目标值，最后一个数字大于目标值，则答案才可能在该行 # 所以如果matrix[i][0]>target或者matrix[i][n-1]<target，都直接跳过 if matrix[i][0] > target or matrix[i][n-1] < target: continue left, right = 0, n-1 while left <= right: mid = (left+right)//2 if target < matrix[i][mid]:  right -= 1 elif target > matrix[i][mid]:  left += 1 else:  return True return False