13 篇博文含有标签「二分查找」

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 <= 10⁵
1 <= spells[i], potions[i] <= 10⁵
1 <= success <= 10¹⁰

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、题干

给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中元素之和小于等于 queries[i] 的 子序列 的最大长度。

子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。

示例 1：

输入：nums = [4,5,2,1], queries = [3,10,21]
输出：[2,3,4]
解释：queries 对应的 answer 如下：
- 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。
- 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。
- 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 。

示例 2：

输入：nums = [2,3,4,5], queries = [1]
输出：[0]
解释：空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。

提示：

n == nums.length
m == queries.length
1 <= n, m <= 1000
1 <= nums[i], queries[i] <= 10⁶

2、思路1-暴力

对 nums 升序排序，求前缀和
暴力查找不大于 queries[i] 的前缀和数量

3、代码

function answerQueries(nums: number[], queries: number[]): number[] {
    nums.sort((a, b) => a - b);
    for (let i = 1; i < nums.length; i++) nums[i] += nums[i - 1];

    let ans = queries.map(Number);
    for (let i = 0; i < queries.length; i++) {
        if (nums.at(-1) <= queries[i]) ans[i] = nums.length;
        else ans[i] = nums.findIndex((s) => s > queries[i]);
    }

    return ans;
};

4、复杂度

时间复杂度： $O(n^2)$
空间复杂度： $O(\log{n})$

5、执行结果

6、思路2-排序优化

在思路1的基础上进行优化，如果 queries 是升序数组，那么查找子序列就不用每次都从头到尾遍历前缀和数组，可以从上一个找到的前缀和下标开始往后查找，查找过程复杂度从 $O(n^2)$ 降到 $O(n)$

7、代码

function answerQueries(nums: number[], queries: number[]): number[] {
    nums.sort((a, b) => a - b);
    for (let i = 1; i < nums.length; i++) nums[i] += nums[i - 1];

    const qs = queries.map((n, i) => [n, i]).sort((a, b) => a[0] - b[0]);

    let ans = queries.map(Number);
    for (let i = 0, j = 0; i < qs.length; i++) {
        if (nums.at(-1) <= qs[i][0]) {
            ans[qs[i][1]] = nums.length;
            continue;
        }

        while (nums[j] <= qs[i][0]) j++;
        ans[qs[i][1]] = j;
    }

    return ans;
};

8、复杂度

时间复杂度： $O(n \log{n})$
空间复杂度： $O(n)$

9、执行结果

1、题干

给你一个函数 f(x, y) 和一个目标结果 z，函数公式未知，请你计算方程 f(x,y) == z 所有可能的正整数数对 x 和 y。满足条件的结果数对可以按任意顺序返回。

尽管函数的具体式子未知，但它是单调递增函数，也就是说：

f(x, y) < f(x + 1, y)
f(x, y) < f(x, y + 1)

函数接口定义如下：

interface CustomFunction {
public:
  // Returns some positive integer f(x, y) for two positive integers x and y based on a formula.
  int f(int x, int y);
};

你的解决方案将按如下规则进行评判：

判题程序有一个由 CustomFunction 的 9 种实现组成的列表，以及一种为特定的 z 生成所有有效数对的答案的方法。
判题程序接受两个输入：function_id（决定使用哪种实现测试你的代码）以及目标结果 z 。
判题程序将会调用你实现的 findSolution 并将你的结果与答案进行比较。
如果你的结果与答案相符，那么解决方案将被视作正确答案，即 Accepted 。

示例 1：

输入：function_id = 1, z = 5
输出：[[1,4],[2,3],[3,2],[4,1]]
解释：function_id = 1 暗含的函数式子为 f(x, y) = x + y
以下 x 和 y 满足 f(x, y) 等于 5：
x=1, y=4 -> f(1, 4) = 1 + 4 = 5
x=2, y=3 -> f(2, 3) = 2 + 3 = 5
x=3, y=2 -> f(3, 2) = 3 + 2 = 5
x=4, y=1 -> f(4, 1) = 4 + 1 = 5

示例 2：

输入：function_id = 2, z = 5
输出：[[1,5],[5,1]]
解释：function_id = 2 暗含的函数式子为 f(x, y) = x * y
以下 x 和 y 满足 f(x, y) 等于 5：
x=1, y=5 -> f(1, 5) = 1 * 5 = 5
x=5, y=1 -> f(5, 1) = 5 * 1 = 5

提示：

1 <= function_id <= 9
1 <= z <= 100
题目保证 f(x, y) == z 的解处于 1 <= x, y <= 1000 的范围内。
在 1 <= x, y <= 1000 的前提下，题目保证 f(x, y) 是一个 32 位有符号整数。

题目不难，难的是阅读理解，这题目看了老半天才懂

2、思路1

暴力枚举加上剪枝优化，效果还不错

3、代码

function findSolution(customfunction: CustomFunction, z: number): number[][] {
    let ans = [];

    for (let x = 1; x < 1001; x++) {
        if (customfunction.f(x, 1) > z) break;

        for (let y = 1; y < 1001; y++) {
            if (customfunction.f(x, y) === z) ans.push([x, y]);
            else if (customfunction.f(x, y) > z) break;
        }
    }

    return ans;
};

4、复杂度

时间复杂度： $O(n^2)$
空间复杂度： $O(1)$

5、执行结果

6、思路2

双指针枚举，两个指针相向步进

7、代码

function findSolution(customfunction: CustomFunction, z: number): number[][] {
    let ans = [];

    for (let x = 1, y = 1000; x < 1001 && y > 0; x++) {
        while (y && customfunction.f(x, y) > z) y--;

        if (y && customfunction.f(x, y) === z) {
            ans.push([x, y]);
            y--;
        }
    }

    return ans;
};

8、复杂度

时间复杂度： $O(n)$
空间复杂度： $O(1)$

9、执行结果

1、题干

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要修改数组以供接下来的操作使用。

如果可以将 x 恰好减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴
1 <= x <= 10⁹

2、思路

数组总和 sum 必须大于 x
找 x 转换为找 sum-x，会简单些
滑动窗口找总和为 sum-x 的区间 $(l, r]$ ，区间求和使用前缀和减少时间复杂度

3、代码

function minOperations(nums: number[], x: number): number {
    let sum = 0, preSums = [];
    for (const n of nums) {
        sum += n;
        preSums.push(sum);
    }

    if (sum <= x) return sum < x ? -1 : nums.length;

    x = sum - x;
    let ans = Infinity, l = -1, r = 0;
    while (l <= r) {
        const y = preSums[r] - (preSums[l] ?? 0);
        if (y === x) ans = Math.min(nums.length - r + l, ans);
        y <= x ? r++ : l++;
    }

    return ans < Infinity ? ans : -1;
};

4、复杂度

时间复杂度： $O(n)$
空间复杂度： $O(n)$

5、执行结果

1、题干

给你三个正整数 n、index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums（下标 从 0 开始 计数）：

nums.length == n
nums[i] 是 正整数 ，其中 0 <= i < n
abs(nums[i] - nums[i+1]) <= 1 ，其中 0 <= i < n-1
nums 中所有元素之和不超过 maxSum
nums[index] 的值被 最大化

返回你所构造的数组中的 nums[index] 。

注意：abs(x) 等于 x 的前提是 x >= 0 ；否则，abs(x) 等于 -x 。

示例 1：

输入：n = 4, index = 2,  maxSum = 6
输出：2
解释：数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。

示例 2：

输入：n = 6, index = 1,  maxSum = 10
输出：3

提示：

1 <= n <= maxSum <= 10⁹
0 <= index < n

2、思路

跟官解思路一贪心+二分查找相似，从均值 Math.ceil(maxSum / n) 开始枚举最大元素 nums[index]，然后按照贪心思路计算左右两边元素，其左右两边的元素是公差为 1 的递减的等差数列，递减到 1 之后其他元素都为 1，最后返回使得整个数组之和小于等于 maxSum 的最大 nums[index]。

3、代码

function maxValue(n: number, index: number, maxSum: number): number {
    function sumNums(ak: number, k: number) {
        let sum = 0;
        const a0 = ak - (k - 1);
        
        if (k > 0) {
            if (a0 >= 1) sum += (a0 + ak) * k / 2;
            else {
                sum += (1 + ak) * ak / 2 + (k - ak);
            }
        }

        return sum;
    }

    function search(max: number) {
        let sum = -max;

        // sum:0 ~ index
        sum += sumNums(max, index + 1);

        // sum:index ~ n-1
        sum += sumNums(max, n - index);

        return sum <= maxSum;
    }

    const avg = Math.ceil(maxSum / n);
    for (let c = 0; c > -1; c++) {
        const valid = search(avg + c);
        if (!valid) return avg + c - 1;
    }
};

4、执行结果

1、题干

给定字符串 s 和字符串数组 words, 返回 words[i] 中是s的子序列的单词个数 。

字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。

例如， “ace” 是 “abcde” 的子序列。

示例 1:

输入: s = "abcde", words = ["a","bb","acd","ace"]
输出: 3
解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。

Example 2:

输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
输出: 2

提示:

1 <= s.length <= 5 * 10⁴
1 <= words.length <= 5000
1 <= words[i].length <= 50
words[i]和s 都只由小写字母组成。

Problem: 792. 匹配子序列的单词数

2、思路

二分查找

按字母表顺序把字符串 s 中所有字符的下标升序存入二维数组 idxMatrix
判断数组 words 中任意字符串 w 是否 s 的子序列，只需要判断 w 中任意字符 c 比前一个字符在 s 中的下标更大。其中查找 c 在 s 中的下标时，使用二分查找算法

3、Code

function numMatchingSubseq(s: string, words: string[]): number {
    const CA = 'a'.charCodeAt(0), idxMatrix = new Array(26).fill(0).map(() => []);

    for (let i = 0; i < s.length; i++) {
        const ci = s[i].charCodeAt(0) - CA;
        idxMatrix[ci].push(i);
    }

    function find(nums: number[] = [], k: number) {
        let l = 0, r = nums.length - 1;

        while (l <= r) {
            const m = ((l + r) / 2) >> 0;
            if (nums[m] > k) {
                if (nums[m - 1] > k) r = m - 1;
                else return nums[m];
            } else {
                l = m + 1;
            }
        }

        return -1;
    }

    let res = 0;
    loop: for (const w of words) {
        let preIdx = -1;
        for (const c of w) {
            const ci = c.charCodeAt(0) - CA;
            const ni = find(idxMatrix[ci], preIdx);
            if (ni < 0) continue loop;
            preIdx = ni;
        }
        res++;
    }

    return res;
};

4、复杂度

时间复杂度： $O(n*logn)$
空间复杂度： $O(n)$

5、执行结果

1、题干

给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 0 开始的字符串 s ，它只包含字符 '*' 和 '|' ，其中 '*' 表示一个盘子，'|' 表示一支蜡烛。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [left_i, right_i] 表示 子字符串 s[left_i...right_i] （包含左右端点的字符）。对于每个查询，你需要找到 子字符串中 在 两支蜡烛之间 的盘子的数目。如果一个盘子在 子字符串中 左边和右边都至少有一支蜡烛，那么这个盘子满足在 两支蜡烛之间 。

比方说，s = "||**||**|*" ，查询 [3, 8] ，表示的是子字符串 "*||**|" 。子字符串中在两支蜡烛之间的盘子数目为 2 ，子字符串中右边两个盘子在它们左边和右边都至少有一支蜡烛。

请你返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。

示例 1:

ex-1

输入：s = "**|**|***|", queries = [[2,5],[5,9]]
输出：[2,3]
解释：
- queries[0] 有两个盘子在蜡烛之间。
- queries[1] 有三个盘子在蜡烛之间。

示例 2:

ex-2

输入：s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
输出：[9,0,0,0,0]
解释：
- queries[0] 有 9 个盘子在蜡烛之间。
- 另一个查询没有盘子在蜡烛之间。

提示：

3 <= s.length <= 10⁵
s 只包含字符 '*' 和 '|' 。
1 <= queries.length <= 10⁵
queries[i].length == 2
0 <= left_i <= right_i < s.length

2、解题思路

按题目意思要查找任意区间 [i,j] 内两支蜡烛之间的盘子数量，要解决两个核心问题：

1、查找区间 [i,j] 内最左边和最右边蜡烛的下标 [l,r]
2、求出区间 [l,r] 内的蜡烛数量

问题1采用区间映射解决，使用二维数组 ranges 存储离任意下标 i 最近的左右蜡烛下标，形如 ranges[i] = [li,ri]。对于任意区间 [i,j] 内最左边和最右边蜡烛的下标为 l = ranges[i][1], r = ranges[j][0]

特殊情况 :

左边没有蜡烛时有 ranges[i] = [-1,ri]
右边没有蜡烛时有 ranges[i] = [li,s.length]
该位置是蜡烛时有 ranges[i] = [i,i]

问题2采用前缀和解决，使用数组 sumList 存储蜡烛数量前缀和，对于任意下标 i 而言 sumList[i] 表示 s[0] 到 s[i] 之间的蜡烛数量。对于任意区间 [l,r] 内的蜡烛数量为 sumList[r] - sumList[l]

至此两个核心问题都得以解决，且都能在 $O(1)$ 时间复杂度内求出正解

3、代码

var platesBetweenCandles = function (s, queries) {
    const n = s.length, sumList = new Array(n), ranges = new Array(n);
    let ps = 0, range = [-1, n];

    for (let i = 0; i < n; i++) {
        if (s[i] === '*') {
            ps += 1;
            ranges[i] = range;
        } else {
            range[1] = i;
            ranges[i] = [i, i];
            range = [i, n];
        }

        sumList[i] = ps;
    }

    return queries.map(([i, j]) => {
        const l = ranges[i][1], r = ranges[j][0];
        return l > -1 && r < n && l < r ? sumList[r] - sumList[l] : 0;
    });
};

4、复杂度

时间复杂度： $O(n)$
空间复杂度： $O(n)$

5、执行结果

执行用时: 308 ms
内存消耗: 86.1 MB

LCR 058.我的日程安排表 I

2022年1月13日 · 阅读需 3 分钟

Whilconn

1、题干

请实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内没有其他安排，则可以存储这个新的日程安排。

MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。

当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生重复预订。

每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

请按照以下步骤调用 MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

示例:

输入:
["MyCalendar","book","book","book"]
[[],[10,20],[15,25],[20,30]]
输出: [null,true,false,true]
解释: 
MyCalendar myCalendar = new MyCalendar();
MyCalendar.book(10, 20); // returns true 
MyCalendar.book(15, 25); // returns false ，第二个日程安排不能添加到日历中，因为时间 15 已经被第一个日程安排预定了
MyCalendar.book(20, 30); // returns true ，第三个日程安排可以添加到日历中，因为第一个日程安排并不包含时间 20

提示：

每个测试用例，调用 MyCalendar.book 函数最多不超过 1000次。
0 <= start < end <= 10⁹

注意：本题与主站 729 题相同： https://leetcode-cn.com/problems/my-calendar-i/

2、解题思路

理想解法是使用平衡二叉搜索树，因为其查找和写入的时间复杂度都是 $O(logn)$ ，但是 JS 没有自带这样的数据结构，手写难度较大，因此采用暴力解法实现。

3、复杂度

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

4、代码

var MyCalendar = function () {
    this.matrix = [];
};

MyCalendar.prototype.book = function (start, end) {
    for (let [s, e] of this.matrix) {
        if (!(start > e || end - 1 < s)) return false;
    }
    return this.matrix.push([start, end - 1]), true;
};

5、执行结果

执行用时: 212 ms 内存消耗: 47.3 MB

剑指 Offer II 058.日程表

2022年1月13日 · 阅读需 3 分钟

Whilconn

1、题干

请实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内没有其他安排，则可以存储这个新的日程安排。

当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生重复预订。

请按照以下步骤调用 MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

示例:

输入:
["MyCalendar","book","book","book"]
[[],[10,20],[15,25],[20,30]]
输出: [null,true,false,true]
解释: 
MyCalendar myCalendar = new MyCalendar();
MyCalendar.book(10, 20); // returns true 
MyCalendar.book(15, 25); // returns false ，第二个日程安排不能添加到日历中，因为时间 15 已经被第一个日程安排预定了
MyCalendar.book(20, 30); // returns true ，第三个日程安排可以添加到日历中，因为第一个日程安排并不包含时间 20

提示：

每个测试用例，调用 MyCalendar.book 函数最多不超过 1000次。
0 <= start < end <= 10⁹

注意：本题与主站 729 题相同： https://leetcode-cn.com/problems/my-calendar-i/

2、解题思路

3、复杂度

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

4、代码

var MyCalendar = function () {
    this.matrix = [];
};

MyCalendar.prototype.book = function (start, end) {
    for (let [s, e] of this.matrix) {
        if (!(start > e || end - 1 < s)) return false;
    }
    return this.matrix.push([start, end - 1]), true;
};

5、执行结果

执行用时: 212 ms 内存消耗: 47.3 MB

825.适龄的朋友

2021年12月27日 · 阅读需 5 分钟

Whilconn

1、题干

在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。

如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：

ages[y] <= 0.5 * ages[x] + 7
ages[y] > ages[x]
ages[y] > 100 && ages[x] < 100

否则，x 将会向 y 发送一条好友请求。

注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。

返回在该社交媒体网站上产生的好友请求总数。

示例 1：

输入：ages = [16,16]
输出：2
解释：2 人互发好友请求。

示例 2：

输入：ages = [16,17,18]
输出：2
解释：产生的好友请求为 17 -> 16 ，18 -> 17 。

示例 3：

输入：ages = [20,30,100,110,120]
输出：3
解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。

提示：

n == ages.length
1 <= n <= 2 * 10⁴
1 <= ages[i] <= 120

2、题目分析

交友年龄限制的限制条件转换后，可以理解为：对于任意年龄ages[x]，交友范围的区间是(0.5 * ages[x] + 7,ages[x]]；
由交友范围还可推断出，年龄15岁以下的用户交友范围区间是空集，因此后续编码时可以直接排除15岁以下的数据。

3、解法1-计数排序

对年龄使用计数排序，遍历所有年龄age，累计并更新交友范围区间(0.5 * age + 7,age]内的人数preCount，然后对最终结果res累加当前年龄的交友请求数(preCount - 1) * counts[age]

4、代码

var numFriendRequests = function (ages) {
    const counts = new Array(121).fill(0);
    for (const age of ages) if (age > 14) counts[age]++;
    let preCount = 0, res = 0;
    for (let age = 15; age < counts.length; age++) {
        if (age % 2 === 0) preCount -= counts[((age - 1) / 2 + 8) >> 0];
        preCount += counts[age];
        res += (preCount - 1) * counts[age];
    }
    return res;
};

代码简要说明

if (age % 2 === 0) preCount -= counts[((age - 1) / 2 + 8) >> 0]
- 对于任意年龄age与age-1而言，交友年龄下限分别为counts[(age / 2 + 8) >> 0]、counts[((age - 1) / 2 + 8) >> 0]
- age为奇数时这两个交友年龄下限相同，age为偶数时交友年龄下限比age-1大1
- 因此age为偶数时，需要减去age-1的交友下限人数counts[((age - 1) / 2 + 8) >> 0]
preCount += counts[age]
- 加上当前年龄用户的数量
res += (preCount - 1) * counts[age]
- 当前年龄人数为counts[age]，他们会给交友范围内除自己外的所有人preCount - 1发请求
- 因此有res += (preCount - 1) * counts[age]

5、执行结果

6、解法2-二分查找

先对所有年龄ages进行降序排序，然后遍历所有年龄，对当前年龄的交友年龄下限进行二分查找，累计所有交友请求数。其中，遇到相同年龄时直接跳过并累计其数量same，当年龄不再相同时对最终结果累加same * (same - 1)

该方法存在较多边界条件，处理不当很容易报错，不建议使用该方法实现

7、代码

var numFriendRequests = function (ages) {
    ages.sort((a, b) => b - a);
    let same = 1;
    return ages.reduce((acc, cur, i) => {
        if (cur === ages[i + 1]) same++;
        if (cur <= 14 || (cur === ages[i + 1] && i !== ages.length - 1)) return acc;

        let l = i + 1, r = ages.length - 1;
        while (l < r) {
            const m = Math.floor((l + r) / 2);
            ages[m] <= cur / 2 + 7 ? (r = m - 1) : (l = m + 1);
        }

        acc += same * (same - 1 + Math.max(0, r - i - (ages[r] > cur / 2 + 7 ? 0 : 1)));
        return (same = 1), acc;
    }, 0);
};

8、执行结果

执行用时：124 ms 内存消耗：47.3 MB

1、题干​

2、思路​

3、代码​

1、题干​

2、思路1-暴力​

3、代码​

4、复杂度​

5、执行结果​

6、思路2-排序优化​

7、代码​

8、复杂度​

9、执行结果​

1、题干​

2、思路1​

3、代码​

4、复杂度​

5、执行结果​

6、思路2​

7、代码​

8、复杂度​

9、执行结果​

1、题干​

2、思路​

3、代码​

4、复杂度​

5、执行结果​

1、题干​

2、思路​

3、代码​

4、执行结果​

1、题干​

2、思路​

3、Code​

4、复杂度​

5、执行结果​

1、题干​

2、解题思路​

3、代码​

4、复杂度​

5、执行结果​

1、题干​

2、解题思路​

3、复杂度​

4、代码​

5、执行结果​

1、题干​

2、解题思路​

3、复杂度​

4、代码​

5、执行结果​

1、题干​

2、题目分析​

3、解法1-计数排序​

4、代码​

5、执行结果​

6、解法2-二分查找​

7、代码​

8、执行结果​

1、题干

2、思路

3、代码

1、题干

2、思路1-暴力

3、代码

4、复杂度

5、执行结果

6、思路2-排序优化

7、代码

8、复杂度

9、执行结果

1、题干

2、思路1

3、代码

4、复杂度

5、执行结果

6、思路2

7、代码

8、复杂度

9、执行结果

1、题干

2、思路

3、代码

4、复杂度

5、执行结果

1、题干

2、思路

3、代码

4、执行结果

1、题干

2、思路

3、Code

4、复杂度

5、执行结果

1、题干

2、解题思路

3、代码

4、复杂度

5、执行结果

1、题干

2、解题思路

3、复杂度

4、代码

5、执行结果

1、题干

2、解题思路

3、复杂度

4、代码

5、执行结果

1、题干

2、题目分析

3、解法1-计数排序

4、代码

5、执行结果

6、解法2-二分查找

7、代码

8、执行结果