2774. 数组的上界 🔒

🟢   🔗 力扣 LeetCode

题目

Write code that enhances all arrays such that you can call the upperBound() method on any array and it will return the last index of a given target number. nums is a sorted ascending array of numbers that may contain duplicates. If the target number is not found in the array, return -1.

Example 1:

Input: nums = [3,4,5], target = 5

Output: 2

Explanation: Last index of target value is 2

Example 2:

Input: nums = [1,4,5], target = 2

Output: -1

Explanation: Because there is no digit 2 in the array, return -1.

Example 3:

Input: nums = [3,4,6,6,6,6,7], target = 6

Output: 5

Explanation: Last index of target value is 5

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i], target <= 10^4
• nums is sorted in ascending order.

Follow up: Can you write an algorithm with O(log n) runtime complexity?

题目大意

请你编写代码实现一个数组方法，任何数组都可以调用 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 <= 10^4
• -10^4 <= nums[i], target <= 10^4
• nums 按升序排序。

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

解题思路

由于数组是升序排列的，可以利用二分查找来提高效率，避免线性查找的时间复杂度。

需要在数组中找到目标数字出现的最后一个位置，如果数组中存在多个相同的数字，应返回最后一个出现的位置。所以当每次找到目标值时，要继续向右查找，直到找到最后一个目标值。

1. 初始化：首先设置 left 为 0，right 为数组的最后一个索引。result 用于记录目标值的最后一个索引，初始化为 -1（即目标值未找到）。
2. 二分查找：在 left 小于等于 right 的条件下，使用二分查找不断缩小搜索范围。
   • 如果当前中间位置的值等于目标值，记录该位置，并将 left 移动到 mid + 1，继续向右查找，确保找到目标值的最后位置。
   • 如果当前中间值小于目标值，则向右查找，将 left 更新为 mid + 1。
   • 如果当前中间值大于目标值，则向左查找，将 right 更新为 mid - 1。
3. 返回结果：如果找到了目标值，result 会被更新为目标值的最后位置。如果没有找到，result 会保持为 -1，表示目标值不在数组中。

复杂度分析

• 时间复杂度：O(log n)，因为使用了二分查找方法，每次都将搜索范围减半。
• 空间复杂度：O(1)，因为只用了常数的额外空间。

代码

/**
 * @param {number} target
 * @return {number}
 */
Array.prototype.upperBound = function (target) {
	let left = 0;
	let right = this.length - 1;
	let result = -1;

	// 二分查找
	while (left <= right) {
		const mid = Math.floor((left + right) / 2);

		if (this[mid] === target) {
			result = mid; // 记录当前找到的位置
			left = mid + 1; // 向右继续查找，确保找到最后一个目标值
		} else if (this[mid] < target) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}

	return result; // 返回目标值的最后一个位置，如果未找到返回 -1
};

相关题目

题号	标题	题解	标签	难度	力扣
2619	数组原型对象的最后一个元素	[✓]		🟢	🀄️ 🔗
2624	蜗牛排序	[✓]		🟠	🀄️ 🔗
2631	分组	[✓]		🟠	🀄️ 🔗