算法题2.0
括号生成
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入:n = 1
输出:["()"]
方法思路
要生成所有有效的括号组合,可以使用回溯法(递归)来构建可能的组合。关键在于确保在任何时候右括号的数量不超过左括号的数量,并且总的左括号和右括号数量都等于n。
- 递归生成组合:从空字符串开始,逐步添加左括号或右括号。
- 约束条件:
- 左括号的数量不能超过n。
- 右括号的数量不能超过左括号的数量。
- 终止条件:当字符串长度等于2*n时,将当前组合加入结果列表。
解决代码
function generateParenthesis(n) {
const result = [];
function backtrack(current, open, close) {
if (current.length === 2 * n) {
result.push(current);
return;
}
if (open < n) {
backtrack(current + '(', open + 1, close);
}
if (close < open) {
backtrack(current + ')', open, close + 1);
}
}
backtrack('', 0, 0);
return result;
}
代码解释
- 初始化结果列表:
result
用于存储所有有效的括号组合。 - 回溯函数:
backtrack
函数递归生成可能的组合:current
是当前构建的字符串。open
是当前左括号的数量。close
是当前右括号的数量。
- 添加左括号的条件:如果左括号数量小于n,可以添加一个左括号。
- 添加右括号的条件:如果右括号数量小于左括号数量,可以添加一个右括号。
- 终止条件:当字符串长度达到2*n时,将当前组合加入结果列表。
- 启动回溯:从空字符串开始,初始左括号和右括号数量均为0。
这种方法确保生成的所有括号组合都是有效的,时间复杂度为O(4^n / sqrt(n)),空间复杂度为O(n)用于递归调用栈。
合并 K 个升序链表
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 1:
输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2:
输入:lists = []
输出:[]
示例 3:
输入:lists = [[]]
输出:[]
方法思路
合并K个升序链表可以通过分治法或优先队列(最小堆)来实现。这里我们使用分治法,将问题分解为两两合并链表,逐步合并所有链表。
- 分治法:将链表数组分成两半,递归合并每一半,最后将两个合并后的链表再合并。
- 合并两个链表:使用合并两个有序链表的方法,逐个比较节点值,按升序连接节点。
解决代码
function mergeKLists(lists) {
if (lists.length === 0) return null;
return mergeLists(lists, 0, lists.length - 1);
}
function mergeLists(lists, start, end) {
if (start === end) return lists[start];
const mid = Math.floor((start + end) / 2);
const left = mergeLists(lists, start, mid);
const right = mergeLists(lists, mid + 1, end);
return mergeTwoLists(left, right);
}
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(-1);
let current = dummy;
while (l1 !== null && l2 !== null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 !== null ? l1 : l2;
return dummy.next;
}
代码解释
- 主函数
mergeKLists
:处理边界情况(空数组),然后调用分治函数mergeLists
。 - 分治函数
mergeLists
:- 递归将链表数组分成两半,直到只剩一个链表。
- 合并左右两部分的链表。
- 合并两个链表的函数
mergeTwoLists
:- 使用虚拟头节点简化操作。
- 逐个比较节点值,按升序连接节点。
- 将剩余链表直接连接到合并后的链表末尾。
这种方法的时间复杂度为O(N log K),其中N是所有链表的总节点数,K是链表数量。空间复杂度为O(log K)用于递归调用栈。
删除有序数组中的重复项
给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:
更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。 返回 k 。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过,那么您的题解将被 通过。
示例 1:
输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2:
输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
方法思路
要原地删除有序数组中的重复项,可以使用双指针法。具体步骤如下:
- 初始化指针:使用两个指针
i
和j
,其中i
是慢指针,j
是快指针。初始时,i
指向数组的第一个元素,j
指向第二个元素。 - 遍历数组:快指针
j
遍历数组,比较nums[j]
和nums[i]
的值。- 如果
nums[j]
不等于nums[i]
,说明遇到了新的唯一元素,将i
向后移动一位,并将nums[j]
的值赋给nums[i]
。 - 如果
nums[j]
等于nums[i]
,则继续移动j
,跳过重复元素。
- 如果
- 返回结果:遍历结束后,
i + 1
即为数组中不重复元素的个数。
解决代码
function removeDuplicates(nums) {
if (nums.length === 0) return 0;
let i = 0;
for (let j = 1; j < nums.length; j++) {
if (nums[j] !== nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
代码解释
- 边界条件处理:如果数组为空,直接返回0。
- 初始化指针:
i
初始化为0,指向数组的第一个元素;j
初始化为1,指向第二个元素。 - 遍历数组:快指针
j
从1开始遍历数组:- 当
nums[j]
不等于nums[i]
时,说明nums[j]
是一个新的唯一元素,将i
向后移动一位,并将nums[j]
的值赋给nums[i]
。 - 如果
nums[j]
等于nums[i]
,则j
继续向后移动,跳过重复元素。
- 当
- 返回结果:最终
i + 1
即为数组中不重复元素的个数,因为i
是从0开始计数的索引。
这种方法的时间复杂度为O(n),其中n是数组的长度,因为我们只遍历了一次数组。空间复杂度为O(1),因为我们没有使用额外的存储空间,是原地修改数组。
找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。
示例 1:
输入:haystack = "sadbutsad", needle = "sad"
输出:0
解释:"sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。
示例 2:
输入:haystack = "leetcode", needle = "leeto"
输出:-1
解释:"leeto" 没有在 "leetcode" 中出现,所以返回 -1 。
方法思路
要在字符串 haystack
中找出字符串 needle
的第一个匹配项的下标,可以使用滑动窗口的方法。具体步骤如下:
- 边界条件处理:如果
needle
为空字符串,返回0;如果haystack
的长度小于needle
的长度,返回-1。 - 滑动窗口:遍历
haystack
,从每个可能的起始位置开始,检查是否存在与needle
匹配的子串。 - 匹配检查:对于每个起始位置,逐个字符比较
haystack
的子串和needle
是否完全匹配。 - 返回结果:找到第一个匹配的子串后返回其起始下标;否则返回-1。
解决代码
function strStr(haystack, needle) {
if (needle.length === 0) return 0;
if (haystack.length < needle.length) return -1;
for (let i = 0; i <= haystack.length - needle.length; i++) {
let match = true;
for (let j = 0; j < needle.length; j++) {
if (haystack[i + j] !== needle[j]) {
match = false;
break;
}
}
if (match) {
return i;
}
}
return -1;
}
代码解释
- 边界条件处理:检查
needle
是否为空或haystack
是否比needle
短,直接返回相应结果。 - 滑动窗口遍历:外层循环从
haystack
的每个可能的起始位置开始,内层循环检查从该位置开始的子串是否与needle
匹配。 - 匹配检查:逐个字符比较子串和
needle
,如果发现不匹配的字符,立即跳出内层循环。 - 返回结果:如果找到匹配的子串,返回其起始下标;否则遍历结束后返回-1。
这种方法的时间复杂度为O((n-m+1)*m),其中n是 haystack
的长度,m是 needle
的长度。空间复杂度为O(1),没有使用额外的存储空间。
两数相除
给你两个整数,被除数 dividend 和除数 divisor。将两数相除,要求 不使用 乘法、除法和取余运算。
整数除法应该向零截断,也就是截去(truncate)其小数部分。例如,8.345 将被截断为 8 ,-2.7335 将被截断至 -2 。
返回被除数 dividend 除以除数 divisor 得到的 商 。
注意:假设我们的环境只能存储 32 位 有符号整数,其数值范围是 [−231, 231 − 1] 。本题中,如果商 严格大于 231 − 1 ,则返回 231 − 1 ;如果商 严格小于 -231 ,则返回 -231 。
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333.. ,向零截断后得到 3 。
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333.. ,向零截断后得到 -2 。
方法思路
要实现两数相除而不使用乘法、除法和取余运算,可以使用位运算和减法来模拟除法过程。具体步骤如下:
- 处理符号:确定最终结果的符号,将被除数和除数都转换为正数处理。
- 边界条件:处理溢出情况,如被除数为-2³¹且除数为-1时,结果会超出32位有符号整数范围。
- 位运算加速:通过不断将除数左移(相当于乘以2)来找到一个最大的基数,使得除数乘以该基数不超过被除数。
- 累加结果:从最大的基数开始,依次减去相应的值,并将结果累加。
- 处理符号和溢出:根据之前的符号处理结果,并检查是否溢出。
解决代码
function divide(dividend, divisor) {
if (dividend === -Math.pow(2, 31) && divisor === -1) {
return Math.pow(2, 31) - 1;
}
let negative = (dividend > 0) ^ (divisor > 0) ? true : false;
let dvd = Math.abs(dividend);
let dvs = Math.abs(divisor);
let result = 0;
while (dvd >= dvs) {
let temp = dvs;
let multiple = 1;
while (dvd >= (temp << 1)) {
if (temp << 1 > 0) { // 防止溢出
temp <<= 1;
multiple <<= 1;
} else {
break;
}
}
dvd -= temp;
result += multiple;
}
if (negative) {
result = -result;
}
return Math.min(Math.max(result, -Math.pow(2, 31)), Math.pow(2, 31) - 1);
}
代码解释
- 溢出处理:检查被除数为-2³¹且除数为-1的情况,直接返回2³¹ - 1。
- 符号确定:使用异或运算确定结果的正负,并将被除数和除数都转换为正数处理。
- 位运算加速:通过左移操作(相当于乘以2)快速找到最大的基数,使得除数乘以该基数不超过被除数。
- 累加结果:从最大的基数开始,依次减去相应的值,并将倍数累加到结果中。
- 结果处理:根据符号调整结果,并确保结果在32位有符号整数范围内。
这种方法的时间复杂度为O(log n),其中n是被除数的绝对值,空间复杂度为O(1)。
搜索旋转排序数组
整数数组 nums 按升序排列,数组中的值 互不相同 。
在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。
例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1:
输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
示例 2:
输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1
示例 3:
输入:nums = [1], target = 0
输出:-1
方法思路
要在旋转后的有序数组中高效地查找目标值,可以使用二分查找的变种。旋转后的数组可以被视为两个有序部分,我们需要确定目标值位于哪一部分,然后在该部分中进行二分查找。
- 初始化指针:使用两个指针
left
和right
分别指向数组的起始和末尾。 - 二分查找:
- 计算中间位置
mid
。 - 如果
nums[mid]
等于目标值,直接返回mid
。 - 判断
nums[left]
和nums[mid]
的关系,以确定哪一部分是有序的:- 如果
nums[left] <= nums[mid]
,说明左半部分是有序的。检查目标值是否在左半部分范围内,如果是,调整right
;否则调整left
。 - 否则,右半部分是有序的。检查目标值是否在右半部分范围内,如果是,调整
left
;否则调整right
。
- 如果
- 计算中间位置
- 返回结果:如果找到目标值,返回其下标;否则返回-1。
解决代码
function search(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid;
}
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
代码解释
- 初始化指针:
left
和right
分别初始化为数组的首尾索引。 - 二分查找:
- 计算中间索引
mid
。 - 如果
nums[mid]
等于目标值,直接返回mid
。 - 判断左半部分是否有序:
- 如果是,检查目标值是否在左半部分范围内,调整
right
或left
。 - 否则,检查目标值是否在右半部分范围内,调整
left
或right
。
- 如果是,检查目标值是否在左半部分范围内,调整
- 计算中间索引
- 返回结果:如果循环结束仍未找到目标值,返回-1。
这种方法的时间复杂度为O(log n),空间复杂度为O(1),符合题目要求。
在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:
输入:nums = [], target = 0
输出:[-1,-1]
方法思路
要找到目标值在排序数组中的第一个和最后一个位置,可以使用两次二分查找:
- 查找第一个位置:通过二分查找找到第一个等于目标值的位置。
- 查找最后一个位置:通过二分查找找到最后一个等于目标值的位置。
解决代码
function searchRange(nums, target) {
const findFirst = () => {
let left = 0;
let right = nums.length - 1;
let first = -1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
if (nums[mid] === target) {
first = mid;
}
}
return first;
};
const findLast = () => {
let left = 0;
let right = nums.length - 1;
let last = -1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
if (nums[mid] === target) {
last = mid;
}
}
return last;
};
const firstPos = findFirst();
const lastPos = findLast();
return [firstPos, lastPos];
}
代码解释
查找第一个位置:
- 初始化
left
和right
指针。 - 在二分查找过程中,如果
nums[mid]
大于或等于目标值,移动right
指针;否则移动left
指针。 - 如果
nums[mid]
等于目标值,记录当前位置first
。
- 初始化
查找最后一个位置:
- 初始化
left
和right
指针。 - 在二分查找过程中,如果
nums[mid]
小于或等于目标值,移动left
指针;否则移动right
指针。 - 如果
nums[mid]
等于目标值,记录当前位置last
。
- 初始化
返回结果:将第一个和最后一个位置组合成数组返回。如果未找到目标值,返回
[-1, -1]
。
这种方法的时间复杂度为O(log n),符合题目要求。
有效的数独
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
注意:
一个有效的数独(部分已被填充)不一定是可解的。
只需要根据以上规则,验证已经填入的数字是否有效即可。
空白格用 '.' 表示。
示例 1:
输入:board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出:true
示例 2:
输入:board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出:false
解释:除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
方法思路
要验证一个9x9的数独是否有效,需要检查以下三个条件:
- 每一行中的数字1-9不能重复。
- 每一列中的数字1-9不能重复。
- 每一个3x3宫中的数字1-9不能重复。
我们可以使用三个二维数组来分别记录行、列和宫中数字的出现情况。遍历数独的每一个格子,如果当前数字不是.
,则检查其在对应的行、列和宫中是否已经出现过。如果出现过,则数独无效;否则,标记该数字为已出现。
解决代码
function isValidSudoku(board) {
const rows = new Array(9).fill().map(() => new Set());
const cols = new Array(9).fill().map(() => new Set());
const boxes = new Array(9).fill().map(() => new Set());
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
const num = board[i][j];
if (num === '.') continue;
const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
if (rows[i].has(num) || cols[j].has(num) || boxes[boxIndex].has(num)) {
return false;
}
rows[i].add(num);
cols[j].add(num);
boxes[boxIndex].add(num);
}
}
return true;
}
代码解释
初始化数据结构:
rows
:一个长度为9的数组,每个元素是一个Set
,用于记录每一行中出现的数字。cols
:一个长度为9的数组,每个元素是一个Set
,用于记录每一列中出现的数字。boxes
:一个长度为9的数组,每个元素是一个Set
,用于记录每一个3x3宫中出现的数字。宫的计算方式为Math.floor(i / 3) * 3 + Math.floor(j / 3)
。
遍历数独格子:
- 对于每一个格子
(i, j)
,如果数字是.
,则跳过。 - 计算当前格子所在的宫的索引
boxIndex
。 - 检查当前数字是否已经在对应的行、列或宫中出现过。如果出现过,则返回
false
。 - 如果没有出现过,则将当前数字添加到对应的行、列和宫的
Set
中。
- 对于每一个格子
返回结果:如果遍历完所有格子后没有发现重复的数字,则返回
true
,表示数独有效。
这种方法的时间复杂度为O(1),因为数独的大小固定为9x9。空间复杂度为O(1),因为我们使用了固定大小的数据结构来存储行、列和宫的数字出现情况。
外观数列
「外观数列」是一个数位字符串序列,由递归公式定义:
countAndSay(1) = "1"
countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。
行程长度编码(RLE)是一种字符串压缩方法,其工作原理是通过将连续相同字符(重复两次或更多次)替换为字符重复次数(运行长度)和字符的串联。例如,要压缩字符串 "3322251" ,我们将 "33" 用 "23" 替换,将 "222" 用 "32" 替换,将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。因此压缩后字符串变为 "23321511"。
给定一个整数 n ,返回 外观数列 的第 n 个元素。
示例 1:
输入:n = 4
输出:"1211"
解释:
countAndSay(1) = "1"
countAndSay(2) = "1" 的行程长度编码 = "11"
countAndSay(3) = "11" 的行程长度编码 = "21"
countAndSay(4) = "21" 的行程长度编码 = "1211"
示例 2:
输入:n = 1
输出:"1"
解释:
这是基本情况。
方法思路
要生成外观数列的第n项,可以通过递归或迭代的方式逐步构建每一项。具体步骤如下:
- 基本情况:当n为1时,直接返回"1"。
- 递归或迭代:对于n>1的情况,获取前一项的字符串,然后对其进行行程长度编码(RLE)处理,生成当前项的字符串。
- 行程长度编码:遍历前一项的字符串,统计连续相同字符的个数,然后将个数和字符拼接起来形成新的字符串。
解决代码
function countAndSay(n) {
if (n === 1) return "1";
const prev = countAndSay(n - 1);
let result = "";
let count = 1;
for (let i = 0; i < prev.length; i++) {
if (prev[i] === prev[i + 1]) {
count++;
} else {
result += count + prev[i];
count = 1;
}
}
return result;
}
代码解释
- 基本情况处理:当n等于1时,直接返回字符串"1"。
- 递归调用:对于n>1的情况,递归调用
countAndSay(n - 1)
获取前一项的字符串。 - 行程长度编码:
- 初始化
result
为空字符串,count
为1(至少有一个连续的字符)。 - 遍历前一项的字符串,如果当前字符与下一个字符相同,增加
count
;否则,将count
和当前字符拼接到result
中,并重置count
为1。
- 初始化
- 返回结果:最终生成的字符串即为外观数列的第n项。
这种方法通过递归逐步构建每一项,时间复杂度为O(n * m),其中n是给定的参数,m是字符串的平均长度。空间复杂度为O(n),主要用于递归调用栈。
缺失的第一个正数
给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1:
输入:nums = [1,2,0]
输出:3
解释:范围 [1,2] 中的数字都在数组中。
示例 2:
输入:nums = [3,4,-1,1]
输出:2
解释:1 在数组中,但 2 没有。
示例 3:
输入:nums = [7,8,9,11,12]
输出:1
解释:最小的正数 1 没有出现。
方法思路
要找到未排序数组中缺失的最小正整数,可以使用原地哈希的方法。具体步骤如下:
- 检查1是否存在:首先遍历数组,如果1不存在,则直接返回1。
- 数据预处理:将所有非正数和大于数组长度的数替换为1,因为这些数不会影响结果。
- 原地哈希标记:利用数组索引作为哈希键,将存在的正整数对应的索引位置的值标记为负数,表示该正整数存在。
- 查找缺失的正整数:遍历数组,第一个正数所在的索引即为缺失的最小正整数。如果所有位置都为负数,则返回数组长度加1。
解决代码
function firstMissingPositive(nums) {
const n = nums.length;
// 检查1是否存在
let containsOne = false;
for (const num of nums) {
if (num === 1) {
containsOne = true;
break;
}
}
if (!containsOne) return 1;
// 数据预处理
for (let i = 0; i < n; i++) {
if (nums[i] <= 0 || nums[i] > n) {
nums[i] = 1;
}
}
// 原地哈希标记
for (let i = 0; i < n; i++) {
const num = Math.abs(nums[i]);
if (num === n) {
nums[0] = -Math.abs(nums[0]);
} else {
nums[num] = -Math.abs(nums[num]);
}
}
// 查找缺失的正整数
for (let i = 1; i < n; i++) {
if (nums[i] > 0) {
return i;
}
}
if (nums[0] > 0) {
return n;
}
return n + 1;
}
代码解释
- 检查1是否存在:遍历数组,如果1不存在,则缺失的最小正整数就是1。
- 数据预处理:将所有非正数和大于数组长度的数替换为1,因为这些数不会影响结果。
- 原地哈希标记:利用数组索引作为哈希键,将存在的正整数对应的索引位置的值标记为负数。注意处理数组长度n的特殊情况。
- 查找缺失的正整数:遍历数组,第一个正数所在的索引即为缺失的最小正整数。如果所有位置都为负数,则返回数组长度加1。
这种方法的时间复杂度为O(n),空间复杂度为O(1),符合题目要求。