#P4076. 在排序数组中查找元素的第一个和最后一个位置
-
ID: 2317
Tried: 69
Accepted: 25
Difficulty: 4
在排序数组中查找元素的第一个和最后一个位置
题目内容
给定一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(logn) 的算法解决此问题。
输入描述
- 第一行输入整数 n，表示数组的长度。
- 第二行输入 n 个整数，表示数组
nums。 - 第三行输入一个整数
target，表示要查找的目标值。
输出描述
- 输出一行，包含两个整数，表示
target在数组中的起始位置和结束位置。如果target不在数组中，则输出-1 -1。
样例
样例 1
输入
6
5 7 7 8 8 10
8
输出
3 4
样例 2
输入
6
5 7 7 8 8 10
6
输出
-1 -1
提示
- 0≤n≤105
- −109≤nums[i]≤109
nums是一个非递减数组- −109≤target≤109
寻找目标值的起始和结束位置
题解思路
1. 观察题目特性
- 数组
nums是 非递减排序 的，这意味着可以利用 二分查找 进行优化。 - 我们需要 找到目标值的左边界和右边界，可以使用 两次二分查找 分别确定。
2. 采用二分查找的方法
寻找左边界：
- 进行二分查找，如果
nums[mid] == target，则继续在左半部分查找，确保找到最左侧的target。 - 终止条件是
left指向target第一次出现的位置。
寻找右边界：
- 进行二分查找，如果
nums[mid] == target，则继续在右半部分查找，确保找到最右侧的target。 - 终止条件是
right指向target最后一次出现的位置。
复杂度分析
- 每次二分查找的时间复杂度为 O(logn)，两次二分查找总共的时间复杂度仍然是 O(logn)。
- 空间复杂度为 O(1)，因为我们仅使用了常数额外空间。
代码实现
Python 实现
import sys
def find_first_and_last(nums, target):
# 寻找左边界
def find_left():
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] >= target: # 继续向左找
right = mid - 1
else:
left = mid + 1
return left
# 寻找右边界
def find_right():
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] > target: # 继续向左找
right = mid - 1
else:
left = mid + 1
return right
left_index = find_left()
if left_index >= len(nums) or nums[left_index] != target:
return [-1, -1]
right_index = find_right()
return [left_index, right_index]
# 读取输入
n = int(sys.stdin.readline().strip())
if n == 0:
print("-1 -1")
else:
nums = list(map(int, sys.stdin.readline().split()))
target = int(sys.stdin.readline().strip())
result = find_first_and_last(nums, target)
print(f"{result[0]} {result[1]}")
Java 实现
import java.util.Scanner;
public class Main {
public static int[] searchRange(int[] nums, int target) {
return new int[]{findLeft(nums, target), findRight(nums, target)};
}
// 找到 target 的左边界
private static int findLeft(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid - 1; // 继续向左找
} else {
left = mid + 1;
}
}
return (left < nums.length && nums[left] == target) ? left : -1;
}
// 找到 target 的右边界
private static int findRight(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1; // 继续向左找
} else {
left = mid + 1;
}
}
return (right >= 0 && nums[right] == target) ? right : -1;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
if (n == 0) {
System.out.println("-1 -1");
return;
}
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}
int target = scanner.nextInt();
int[] result = searchRange(nums, target);
System.out.println(result[0] + " " + result[1]);
}
}
C++ 实现
#include <iostream>
#include <vector>
using namespace std;
// 找到左边界
int findLeft(const vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid - 1; // 继续向左找
} else {
left = mid + 1;
}
}
return (left < nums.size() && nums[left] == target) ? left : -1;
}
// 找到右边界
int findRight(const vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1; // 继续向左找
} else {
left = mid + 1;
}
}
return (right >= 0 && nums[right] == target) ? right : -1;
}
// 主函数
int main() {
int n;
cin >> n;
if (n == 0) {
cout << "-1 -1" << endl;
return 0;
}
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
int target;
cin >> target;
int left = findLeft(nums, target);
int right = findRight(nums, target);
cout << left << " " << right << endl;
return 0;
}