131 篇博文 含有标签「数组」

1、题干​

给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵 mat 。arr 和 mat 都包含范围 [1，m * n] 内的 所有 整数。

从下标 0 开始遍历 arr 中的每个下标 i ，并将包含整数 arr[i] 的 mat 单元格涂色。

请你找出 arr 中第一个使得 mat 的某一行或某一列都被涂色的元素，并返回其下标 i 。

示例 1：

输入：arr = [1,3,4,2], mat = [[1,4],[2,3]]
输出：2
解释：遍历如上图所示，arr[2] 在矩阵中的第一行或第二列上都被涂色。

示例 2：

输入：arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
输出：3
解释：遍历如上图所示，arr[3] 在矩阵中的第二列上都被涂色。

提示：

• m == mat.length
• n = mat[i].length
• arr.length == m * n
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• 1 <= arr[i], mat[r][c] <= m * n
• arr 中的所有整数 互不相同
• mat 中的所有整数 互不相同

2、思路​

模拟题，对行列涂色计数即可

3、代码​

function firstCompleteIndex(arr: number[], mat: number[][]): number {
    const map = new Array(arr.length + 1);
    for (let i = 0; i < mat.length; i++) {
        for (let j = 0; j < mat[i].length; j++) {
            map[mat[i][j]] = [i, j];
        }
    }

    const rows = new Array(mat.length).fill(0), cols = new Array(mat[0].length).fill(0);
    for (let i = 0; i < arr.length; i++) {
        const [r, c] = map[arr[i]];
        rows[r]++, cols[c]++;
        if (rows[r] === mat[0].length || cols[c] === mat.length) return i;
    }

    return -1;
};

1、题干​

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder 和 postorder 都由 不同 的值组成
• postorder 中每一个值都在 inorder 中
• inorder 保证是树的中序遍历
• postorder 保证是树的后序遍历

2、思路​

后序遍历数组最后一个元素是根节点，中序遍历数组中根节点前、后两边分别是左子树与右子树，根据这两个性质递归即可，时间复杂度最优 $O(n\log{n})$，最差 $O(n^2)$

3、代码​

function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
    if (!inorder.length) return null;

    const rv = postorder.at(-1);
    const root = new TreeNode(rv);

    const c = inorder.indexOf(rv);

    const inLeft = inorder.slice(0, c);
    const inRight = inorder.slice(c + 1);

    const postLeft = postorder.slice(0, c);
    const postRight = postorder.slice(c, postorder.length - 1);

    root.left = buildTree(inLeft, postLeft);
    root.right = buildTree(inRight, postRight);

    return root;
}

1、题干​

给你一个下标从 0 开始的整数数组 nums ，如果满足下述条件，则认为数组 nums 是一个 美丽数组 ：

• nums.length 为偶数
• 对所有满足 i % 2 == 0 的下标 i ，nums[i] != nums[i + 1] 均成立

注意，空数组同样认为是美丽数组。

你可以从 nums 中删除任意数量的元素。当你删除一个元素时，被删除元素右侧的所有元素将会向左移动一个单位以填补空缺，而左侧的元素将会保持 不变 。

返回使 nums 变为美丽数组所需删除的 最少 元素数目。

示例 1：

输入：nums = [1,1,2,3,5]
输出：1
解释：可以删除 nums[0] 或 nums[1] ，这样得到的 nums = [1,2,3,5] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 1 个元素。

示例 2：

输入：nums = [1,1,2,2,3,3]
输出：2
解释：可以删除 nums[0] 和 nums[5] ，这样得到的 nums = [1,2,2,3] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 2 个元素。

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105

2、思路​

模拟一遍删除过程就能过。其他题解说是贪心，也有证明过程，看完还是不懂不理解。这题证明比AC难得多。

3、代码​

function minDeletion(nums: number[]): number {
    let cur = -Infinity, size = 0;
    
    for (const k of nums) {
        if (size % 2 === 0 || k !== cur) cur = k, size++;
    }

    return nums.length - size + (size % 2);
};

1、题干​

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

2、思路​

两种思路：双指针，合并后排序（无脑暴力）

3、代码​

• 双指针

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    const arr1 = nums1.slice(0, m), arr2 = nums2;

    for (let k = 0, i = 0, j = 0; k < m + n; k++) {
        nums1[k] = j >= n || arr1[i] <= arr2[j] ? arr1[i++] : arr2[j++];
    }
};

官解的逆向双指针更优秀，空间复杂度为 $O(1)$，即不需要另外开辟数组辅助，而是优先将结果填充到 nums1 尾部区域

• 合并排序

var merge = function (nums1, m, nums2, n) {
    nums1.splice(m, n, ...nums2);
    return nums1.sort((a, b) => a - b);
};

1、题干​

给你一个下标从 0 开始的整数数组 nums 和一个整数 threshold 。

请你从 nums 的子数组中找出以下标 l 开头、下标 r 结尾 (0 <= l <= r < nums.length) 且满足以下条件的 最长子数组 ：

• nums[l] % 2 == 0
• 对于范围 [l, r - 1] 内的所有下标 i ，nums[i] % 2 != nums[i + 1] % 2
• 对于范围 [l, r] 内的所有下标 i ，nums[i] <= threshold

以整数形式返回满足题目要求的最长子数组的长度。

注意：子数组 是数组中的一个连续非空元素序列。

示例 1：

输入：nums = [3,2,5,4], threshold = 5
输出：3
解释：在这个示例中，我们选择从 l = 1 开始、到 r = 3 结束的子数组 => [2,5,4] ，满足上述条件。
因此，答案就是这个子数组的长度 3 。可以证明 3 是满足题目要求的最大长度。

示例 2：

输入：nums = [1,2], threshold = 2
输出：1
解释：
在这个示例中，我们选择从 l = 1 开始、到 r = 1 结束的子数组 => [2] 。
该子数组满足上述全部条件。可以证明 1 是满足题目要求的最大长度。

示例 3：

输入：nums = [2,3,4,5], threshold = 4
输出：3
解释：
在这个示例中，我们选择从 l = 0 开始、到 r = 2 结束的子数组 => [2,3,4] 。 
该子数组满足上述全部条件。
因此，答案就是这个子数组的长度 3 。可以证明 3 是满足题目要求的最大长度。

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= threshold <= 100

2、思路​

双指针，暴力枚举

3、代码​

• 双指针，时间复杂度 $O(n)$

function longestAlternatingSubarray(nums: number[], threshold: number): number {
    let ans = 0;

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] % 2 !== 0 || nums[i] > threshold) continue;

        let j = i + 1;
        while (j < nums.length && nums[j] <= threshold && nums[j] % 2 !== nums[j - 1] % 2) {
            j++;
        }

        ans = Math.max(ans, j - i);
        i = j - 1;
    }

    return ans;
};

• 暴力枚举，时间复杂度 $O(n^2)$

function longestAlternatingSubarray(nums: number[], threshold: number): number {
    let ans = 0;

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] % 2 !== 0) continue;

        for (let j = i; j < nums.length && nums[j] <= threshold; j++) {
            ans = Math.max(ans, j - i + 1);
            if (nums[j] % 2 === nums[j + 1] % 2) break;
        }
    }

    return ans;
};

1、题干​

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你需要执行以下操作 恰好 k 次，最大化你的得分：

1. 从 nums 中选择一个元素 m 。
2. 将选中的元素 m 从数组中删除。
3. 将新元素 m + 1 添加到数组中。
4. 你的得分增加 m 。

请你返回执行以上操作恰好 k 次后的最大得分。

示例 1：

输入：nums = [1,2,3,4,5], k = 3
输出：18
解释：我们需要从 nums 中恰好选择 3 个元素并最大化得分。
第一次选择 5 。和为 5 ，nums = [1,2,3,4,6] 。
第二次选择 6 。和为 6 ，nums = [1,2,3,4,7] 。
第三次选择 7 。和为 5 + 6 + 7 = 18 ，nums = [1,2,3,4,8] 。
所以我们返回 18 。
18 是可以得到的最大答案。

示例 2：

输入：nums = [5,5,5], k = 2
输出：11
解释：我们需要从 nums 中恰好选择 2 个元素并最大化得分。
第一次选择 5 。和为 5 ，nums = [5,5,6] 。
第二次选择 6 。和为 6 ，nums = [5,5,7] 。
所以我们返回 11 。
11 是可以得到的最大答案。

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 100

2、思路​

根据题意可知 k 次得分是首项为 Math.max(...nums) 公差为 $1$ 的等差数列，套用等差数列求和公式即可

3、代码​

function maximizeSum(nums: number[], k: number): number {
    return k * (2 * Math.max(...nums) + k - 1) / 2;
};

1、题干​

给你一个数组 nums ，请你完成两类查询。

1. 其中一类查询要求 更新 数组 nums 下标对应的值
2. 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right

实现 NumArray 类：

• NumArray(int[] nums) 用整数数组 nums 初始化对象
• void update(int index, int val) 将 nums[index] 的值 更新 为 val
• int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]）

示例 1：

输入：
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出：
[null, 9, null, 8]

解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8

提示：

• 1 <= nums.length <= 3 * 104
• -100 <= nums[i] <= 100
• 0 <= index < nums.length
• -100 <= val <= 100
• 0 <= left <= right < nums.length
• 调用 update 和 sumRange 方法次数不大于 3 * 104 

2、思路​

树状数组

3、代码​

class NumArray {
    treeNums = [];

    constructor(nums: number[]) {
        const sums = new Array(nums.length + 1).fill(0);
        this.treeNums = new Array(nums.length + 1).fill(0);

        for (let i = 1; i < sums.length; i++) {
            sums[i] = nums[i - 1] + sums[i - 1];
            this.treeNums[i] = sums[i] - sums[i - this.lowbit(i)];
        }
    }

    lowbit(i: number) {
        return i & -i;
    }

    sum(r: number) {
        let ans = 0;

        while (r > 0) {
            ans += this.treeNums[r];
            r = r - this.lowbit(r);
        }

        return ans;
    }

    update(i: number, val: number): void {
        const d = val - this.sumRange(i, i);

        i += 1;
        while (i < this.treeNums.length) {
            this.treeNums[i] += d;
            i = i + this.lowbit(i);
        }
    }

    sumRange(left: number, right: number): number {
        left += 1, right += 1;
        return this.sum(right) - this.sum(left - 1);
    }
}

1、题干​

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。

同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。

请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。

示例 1：

输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出：[4,0,3]
解释：
- 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
- 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
- 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
所以返回 [4,0,3] 。

示例 2：

输入：spells = [3,1,2], potions = [8,5,8], success = 16
输出：[2,0,2]
解释：
- 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
- 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
- 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
所以返回 [2,0,2] 。

提示：

• n == spells.length
• m == potions.length
• 1 <= n, m <= 105
• 1 <= spells[i], potions[i] <= 105
• 1 <= success <= 1010

2、思路​

对 potions 排序，遍历 spells 并使用二分查找统计 potions 中不小于 success / spells[i] 的元素数量，复杂度 $O(n\log{n})$

3、代码​

function successfulPairs(spells: number[], potions: number[], success: number): number[] {
    potions.sort((a, b) => a - b);
    const pairs = new Array(spells.length).fill(0);

    for (let i = 0; i < spells.length; i++) {
        const s = success / spells[i];
        pairs[i] = search(potions, s);
    }

    return pairs;
};

function search(arr: number[], k: number) {
    let m = 0, l = 0, r = arr.length - 1;
    while (l <= r) {
        m = (l + r) >> 1;

        if (arr[m] >= k) {
            r = m - 1;
        } else {
            l = m + 1;
        }
    }

    return arr.length - l;
}

1、题干​

给你一个 非严格递增排列 的数组 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 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按 非严格递增 排列

2、思路​

遍历数组累计唯一数字数量 c，c 作为唯一元素下标用于原地修改数组

3、Code​

function removeDuplicates(nums: number[]): number {
    let c = 1;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] !== nums[i - 1]) {
            nums[c] = nums[i];
            c += 1;
        }
    }

    return c;
};

1、题干​

给你一个下标从 0 开始的正整数数组 nums 。请你找出并统计满足下述条件的三元组 (i, j, k) 的数目：

• 0 <= i < j < k < nums.length
• nums[i]、nums[j] 和 nums[k] 两两不同 。
  • 换句话说：nums[i] != nums[j]、nums[i] != nums[k] 且 nums[j] != nums[k] 。

返回满足上述条件三元组的数目。

示例 1：

输入：nums = [4,4,2,4,3]
输出：3
解释：下面列出的三元组均满足题目条件：
- (0, 2, 4) 因为 4 != 2 != 3
- (1, 2, 4) 因为 4 != 2 != 3
- (2, 3, 4) 因为 2 != 4 != 3
共计 3 个三元组，返回 3 。
注意 (2, 0, 4) 不是有效的三元组，因为 2 > 0 。

示例 2：

输入：nums = [1,1,1,1,1]
输出：0
解释：不存在满足条件的三元组，所以返回 0 。

提示：

• 3 <= nums.length <= 100
• 1 <= nums[i] <= 1000

2、思路​

• 枚举：3重循环枚举所有不等三元组
• 哈希表：对数组所有元素计数，枚举累计所有不等三元组

3、代码​

use std::collections::HashMap;

impl Solution {
    pub fn unequal_triplets(nums: Vec<i32>) -> i32 {
        let len = nums.len();
        let mut map = HashMap::new();
        for n in nums {
            let c = map.entry(n).or_insert(0);
            *c += 1;
        }

        let mut ans = 0;
        let mut pc = 0;
        for (k, c) in map {
            ans += pc * c * (len - pc - c);
            pc += c;
        }

        return ans as i32;
    }
}

function unequalTriplets(nums: number[]): number {
    const map = new Map<number, number>();
    for (let i = 0; i < nums.length; i++) {
        map.set(nums[i], (map.get(nums[i]) || 0) + 1);
    }

    let ans = 0, pc = 0;

    for (const [_, c] of map) {
        ans += pc * c * (nums.length - pc - c);
        pc += c;
    }

    return ans;
};

function unequalTriplets(nums: number[]): number {
    let ans = 0;

    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            for (let k = j + 1; k < nums.length; k++) {
                if (nums[i] !== nums[j] && nums[i] !== nums[k] && nums[j] !== nums[k]) ans += 1;
            }
        }
    }

    return ans;
};