跳转至

2774. 数组的上界 🔒

题目描述

请你编写代码实现一个数组方法，任何数组都可以调用 upperBound() 方法，并返回给定目标数字的最后一个索引。nums 是一个可能包含重复数字的按升序排序的数组。如果在数组中找不到目标数字，则返回-1。

 

示例 1：

输入：nums = [3,4,5], target = 5
输出：2
解释：目标值的最后一个索引是 2

示例 2：

输入：nums = [1,4,5], target = 2
输出：-1
解释：因为数组中没有数字 2，所以返回 -1。

示例 3：

输入：nums = [3,4,6,6,6,6,7], target = 6
输出：5
解释：目标值的最后一个索引是 5

 

提示：

  • 1 <= nums.length <= 104
  • -104 <= nums[i], target <= 104
  • nums 按升序排序。

 

进阶：你能编写一个时间复杂度为 O(log n) 的算法吗？

解法

方法一：二分查找

思考

有序数组上求 \(target\) 最后一次出现的下标。从右线性扫描可以得到答案，题目同时允许对数时间。

二分出第一个大于 \(target\) 的位置，其前一位若等于 \(target\) 即为右边界，否则不存在。

数组已升序，用二分找到第一个大于 \(\textit{target}\) 的位置，再判断其前一个元素是否等于 \(\textit{target}\)。若相等则该下标即为最后一次出现的位置，否则返回 \(-1\)。

时间复杂度 \(O(\log n)\)，空间复杂度 \(O(1)\)。其中 \(n\) 为数组长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
declare global {
    interface Array<T> {
        upperBound(target: number): number;
    }
}

Array.prototype.upperBound = function (target: number) {
    let left = 0;
    let right = this.length;
    while (left < right) {
        const mid = (left + right) >> 1;
        if (this[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left > 0 && this[left - 1] == target ? left - 1 : -1;
};

// [3,4,5].upperBound(5); // 2
// [1,4,5].upperBound(2); // -1
// [3,4,6,6,6,6,7].upperBound(6) // 5

方法二：线性扫描

思考

二分换来对数时间，却多了边界判断。\(lastIndexOf\) 从右一次扫描即可，实现更短，最坏线性。

直接调用 lastIndexOf 从右向左扫描，返回目标值的最后一次下标；不存在则返回 \(-1\)。

时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。其中 \(n\) 为数组长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
declare global {
    interface Array<T> {
        upperBound(target: number): number;
    }
}

Array.prototype.upperBound = function (target: number) {
    return this.lastIndexOf(target);
};

// [3,4,5].upperBound(5); // 2
// [1,4,5].upperBound(2); // -1
// [3,4,6,6,6,6,7].upperBound(6) // 5

评论