跳转到内容

算法题2.0

括号生成

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

输入:n = 3

输出:["((()))","(()())","(())()","()(())","()()()"]

示例 2:

输入:n = 1

输出:["()"]

方法思路

要生成所有有效的括号组合,可以使用回溯法(递归)来构建可能的组合。关键在于确保在任何时候右括号的数量不超过左括号的数量,并且总的左括号和右括号数量都等于n。

  1. 递归生成组合:从空字符串开始,逐步添加左括号或右括号。
  2. 约束条件
    • 左括号的数量不能超过n。
    • 右括号的数量不能超过左括号的数量。
  3. 终止条件:当字符串长度等于2*n时,将当前组合加入结果列表。

解决代码

javascript
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;
}

代码解释

  1. 初始化结果列表result 用于存储所有有效的括号组合。
  2. 回溯函数backtrack 函数递归生成可能的组合:
    • current 是当前构建的字符串。
    • open 是当前左括号的数量。
    • close 是当前右括号的数量。
  3. 添加左括号的条件:如果左括号数量小于n,可以添加一个左括号。
  4. 添加右括号的条件:如果右括号数量小于左括号数量,可以添加一个右括号。
  5. 终止条件:当字符串长度达到2*n时,将当前组合加入结果列表。
  6. 启动回溯:从空字符串开始,初始左括号和右括号数量均为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个升序链表可以通过分治法或优先队列(最小堆)来实现。这里我们使用分治法,将问题分解为两两合并链表,逐步合并所有链表。

  1. 分治法:将链表数组分成两半,递归合并每一半,最后将两个合并后的链表再合并。
  2. 合并两个链表:使用合并两个有序链表的方法,逐个比较节点值,按升序连接节点。

解决代码

javascript
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;
}

代码解释

  1. 主函数 mergeKLists:处理边界情况(空数组),然后调用分治函数 mergeLists
  2. 分治函数 mergeLists
    • 递归将链表数组分成两半,直到只剩一个链表。
    • 合并左右两部分的链表。
  3. 合并两个链表的函数 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 。不需要考虑数组中超出新长度后面的元素。

方法思路

要原地删除有序数组中的重复项,可以使用双指针法。具体步骤如下:

  1. 初始化指针:使用两个指针 ij,其中 i 是慢指针,j 是快指针。初始时,i 指向数组的第一个元素,j 指向第二个元素。
  2. 遍历数组:快指针 j 遍历数组,比较 nums[j]nums[i] 的值。
    • 如果 nums[j] 不等于 nums[i],说明遇到了新的唯一元素,将 i 向后移动一位,并将 nums[j] 的值赋给 nums[i]
    • 如果 nums[j] 等于 nums[i],则继续移动 j,跳过重复元素。
  3. 返回结果:遍历结束后,i + 1 即为数组中不重复元素的个数。

解决代码

javascript
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;
}

代码解释

  1. 边界条件处理:如果数组为空,直接返回0。
  2. 初始化指针i 初始化为0,指向数组的第一个元素;j 初始化为1,指向第二个元素。
  3. 遍历数组:快指针 j 从1开始遍历数组:
    • nums[j] 不等于 nums[i] 时,说明 nums[j] 是一个新的唯一元素,将 i 向后移动一位,并将 nums[j] 的值赋给 nums[i]
    • 如果 nums[j] 等于 nums[i],则 j 继续向后移动,跳过重复元素。
  4. 返回结果:最终 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 的第一个匹配项的下标,可以使用滑动窗口的方法。具体步骤如下:

  1. 边界条件处理:如果 needle 为空字符串,返回0;如果 haystack 的长度小于 needle 的长度,返回-1。
  2. 滑动窗口:遍历 haystack,从每个可能的起始位置开始,检查是否存在与 needle 匹配的子串。
  3. 匹配检查:对于每个起始位置,逐个字符比较 haystack 的子串和 needle 是否完全匹配。
  4. 返回结果:找到第一个匹配的子串后返回其起始下标;否则返回-1。

解决代码

javascript
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;
}

代码解释

  1. 边界条件处理:检查 needle 是否为空或 haystack 是否比 needle 短,直接返回相应结果。
  2. 滑动窗口遍历:外层循环从 haystack 的每个可能的起始位置开始,内层循环检查从该位置开始的子串是否与 needle 匹配。
  3. 匹配检查:逐个字符比较子串和 needle,如果发现不匹配的字符,立即跳出内层循环。
  4. 返回结果:如果找到匹配的子串,返回其起始下标;否则遍历结束后返回-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 。

方法思路

要实现两数相除而不使用乘法、除法和取余运算,可以使用位运算和减法来模拟除法过程。具体步骤如下:

  1. 处理符号:确定最终结果的符号,将被除数和除数都转换为正数处理。
  2. 边界条件:处理溢出情况,如被除数为-2³¹且除数为-1时,结果会超出32位有符号整数范围。
  3. 位运算加速:通过不断将除数左移(相当于乘以2)来找到一个最大的基数,使得除数乘以该基数不超过被除数。
  4. 累加结果:从最大的基数开始,依次减去相应的值,并将结果累加。
  5. 处理符号和溢出:根据之前的符号处理结果,并检查是否溢出。

解决代码

javascript
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);
}

代码解释

  1. 溢出处理:检查被除数为-2³¹且除数为-1的情况,直接返回2³¹ - 1。
  2. 符号确定:使用异或运算确定结果的正负,并将被除数和除数都转换为正数处理。
  3. 位运算加速:通过左移操作(相当于乘以2)快速找到最大的基数,使得除数乘以该基数不超过被除数。
  4. 累加结果:从最大的基数开始,依次减去相应的值,并将倍数累加到结果中。
  5. 结果处理:根据符号调整结果,并确保结果在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

方法思路

要在旋转后的有序数组中高效地查找目标值,可以使用二分查找的变种。旋转后的数组可以被视为两个有序部分,我们需要确定目标值位于哪一部分,然后在该部分中进行二分查找。

  1. 初始化指针:使用两个指针 leftright 分别指向数组的起始和末尾。
  2. 二分查找
    • 计算中间位置 mid
    • 如果 nums[mid] 等于目标值,直接返回 mid
    • 判断 nums[left]nums[mid] 的关系,以确定哪一部分是有序的:
      • 如果 nums[left] <= nums[mid],说明左半部分是有序的。检查目标值是否在左半部分范围内,如果是,调整 right;否则调整 left
      • 否则,右半部分是有序的。检查目标值是否在右半部分范围内,如果是,调整 left;否则调整 right
  3. 返回结果:如果找到目标值,返回其下标;否则返回-1。

解决代码

javascript
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;
}

代码解释

  1. 初始化指针leftright 分别初始化为数组的首尾索引。
  2. 二分查找
    • 计算中间索引 mid
    • 如果 nums[mid] 等于目标值,直接返回 mid
    • 判断左半部分是否有序:
      • 如果是,检查目标值是否在左半部分范围内,调整 rightleft
      • 否则,检查目标值是否在右半部分范围内,调整 leftright
  3. 返回结果:如果循环结束仍未找到目标值,返回-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]

方法思路

要找到目标值在排序数组中的第一个和最后一个位置,可以使用两次二分查找:

  1. 查找第一个位置:通过二分查找找到第一个等于目标值的位置。
  2. 查找最后一个位置:通过二分查找找到最后一个等于目标值的位置。

解决代码

javascript
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];
}

代码解释

  1. 查找第一个位置

    • 初始化 leftright 指针。
    • 在二分查找过程中,如果 nums[mid] 大于或等于目标值,移动 right 指针;否则移动 left 指针。
    • 如果 nums[mid] 等于目标值,记录当前位置 first
  2. 查找最后一个位置

    • 初始化 leftright 指针。
    • 在二分查找过程中,如果 nums[mid] 小于或等于目标值,移动 left 指针;否则移动 right 指针。
    • 如果 nums[mid] 等于目标值,记录当前位置 last
  3. 返回结果:将第一个和最后一个位置组合成数组返回。如果未找到目标值,返回 [-1, -1]

这种方法的时间复杂度为O(log n),符合题目要求。

有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。

数字 1-9 在每一列只能出现一次。

数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)

注意:

一个有效的数独(部分已被填充)不一定是可解的。

只需要根据以上规则,验证已经填入的数字是否有效即可。

空白格用 '.' 表示。

示例 1:

algorithm3.jpg

输入: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. 每一行中的数字1-9不能重复。
  2. 每一列中的数字1-9不能重复。
  3. 每一个3x3宫中的数字1-9不能重复。

我们可以使用三个二维数组来分别记录行、列和宫中数字的出现情况。遍历数独的每一个格子,如果当前数字不是.,则检查其在对应的行、列和宫中是否已经出现过。如果出现过,则数独无效;否则,标记该数字为已出现。

解决代码

javascript
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;
}

代码解释

  1. 初始化数据结构

    • rows:一个长度为9的数组,每个元素是一个Set,用于记录每一行中出现的数字。
    • cols:一个长度为9的数组,每个元素是一个Set,用于记录每一列中出现的数字。
    • boxes:一个长度为9的数组,每个元素是一个Set,用于记录每一个3x3宫中出现的数字。宫的计算方式为Math.floor(i / 3) * 3 + Math.floor(j / 3)
  2. 遍历数独格子

    • 对于每一个格子(i, j),如果数字是.,则跳过。
    • 计算当前格子所在的宫的索引boxIndex
    • 检查当前数字是否已经在对应的行、列或宫中出现过。如果出现过,则返回false
    • 如果没有出现过,则将当前数字添加到对应的行、列和宫的Set中。
  3. 返回结果:如果遍历完所有格子后没有发现重复的数字,则返回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项,可以通过递归或迭代的方式逐步构建每一项。具体步骤如下:

  1. 基本情况:当n为1时,直接返回"1"。
  2. 递归或迭代:对于n>1的情况,获取前一项的字符串,然后对其进行行程长度编码(RLE)处理,生成当前项的字符串。
  3. 行程长度编码:遍历前一项的字符串,统计连续相同字符的个数,然后将个数和字符拼接起来形成新的字符串。

解决代码

javascript
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;
}

代码解释

  1. 基本情况处理:当n等于1时,直接返回字符串"1"。
  2. 递归调用:对于n>1的情况,递归调用countAndSay(n - 1)获取前一项的字符串。
  3. 行程长度编码
    • 初始化result为空字符串,count为1(至少有一个连续的字符)。
    • 遍历前一项的字符串,如果当前字符与下一个字符相同,增加count;否则,将count和当前字符拼接到result中,并重置count为1。
  4. 返回结果:最终生成的字符串即为外观数列的第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。
  2. 数据预处理:将所有非正数和大于数组长度的数替换为1,因为这些数不会影响结果。
  3. 原地哈希标记:利用数组索引作为哈希键,将存在的正整数对应的索引位置的值标记为负数,表示该正整数存在。
  4. 查找缺失的正整数:遍历数组,第一个正数所在的索引即为缺失的最小正整数。如果所有位置都为负数,则返回数组长度加1。

解决代码

javascript
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。
  2. 数据预处理:将所有非正数和大于数组长度的数替换为1,因为这些数不会影响结果。
  3. 原地哈希标记:利用数组索引作为哈希键,将存在的正整数对应的索引位置的值标记为负数。注意处理数组长度n的特殊情况。
  4. 查找缺失的正整数:遍历数组,第一个正数所在的索引即为缺失的最小正整数。如果所有位置都为负数,则返回数组长度加1。

这种方法的时间复杂度为O(n),空间复杂度为O(1),符合题目要求。