上海定制网站开发,千万不要报培训班学室内设计,网站做301跳转需解析,培训心得简短200字原题链接#x1f517;#xff1a;在排序数组中查找元素的第一个和最后一个位置 难度#xff1a;中等⭐️⭐️
题目
给你一个按照非递减顺序排列的整数数组 nums#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标…原题链接在排序数组中查找元素的第一个和最后一个位置 难度中等⭐️⭐️
题目
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1 输入nums [5,7,7,8,8,10], target 8 输出[3,4]
示例 2 输入nums [5,7,7,8,8,10], target 6 输出[-1,-1]
示例 3 输入nums [], target 0 输出[-1,-1]
提示
0 nums.length 105-109 nums[i] 109nums 是一个非递减数组-109 target 109
二分查找 二分查找Binary Search也称为折半搜索是一种在有序数组中查找特定元素的搜索算法。其基本思想是将目标值与数组中间的元素进行比较 如果目标值等于中间元素搜索成功返回该位置。如果目标值小于中间元素搜索范围缩小至数组的左半部分。如果目标值大于中间元素搜索范围缩小至数组的右半部分。这个过程将不断重复直到找到目标值或者搜索范围为空为止。 以下是二分查找算法的一般步骤 初始化设置两个指针一个指向数组的起始位置通常记为 left另一个指向数组的结束位置通常记为 right。 循环条件当 left 小于等于 right 时继续循环。 计算中间位置计算 left 和 right 之间的中间位置 mid通常使用 (left right) / 2。 比较与调整 如果 nums[mid] 等于目标值根据需要返回 mid 或继续搜索以找到更精确的位置。如果 nums[mid] 大于目标值将 right 调整为 mid - 1。如果 nums[mid] 小于目标值将 left 调整为 mid 1。 循环结束如果 left 大于 right则表示目标值不在数组中返回一个特定的值通常是 -1表示未找到。 二分查找的效率非常高时间复杂度为 O(log n)其中 n 是数组的长度。然而它要求数组是有序的并且只能应用于一维有序数组。 下面是一个简单的 C 实现示例
int binarySearch(const std::vectorint nums, int target) {int left 0, right nums.size() - 1;while (left right) {int mid left (right - left) / 2; // 防止溢出if (nums[mid] target) {return mid; // 找到目标值} else if (nums[mid] target) {left mid 1; // 搜索右半部分} else {right mid - 1; // 搜索左半部分}}return -1; // 未找到目标值
}这个函数会返回目标值在数组中的索引如果目标值不在数组中则返回 -1。
题解
解题思路 LeetCode 上的这个问题通常被称为“Find First and Last Position of Element in Sorted Array”题目编号为 34。这个问题可以通过二分查找算法来解决因为数组是已经排序的。 以下是解决这个问题的一般思路 理解问题首先你需要理解问题的要求即在一个升序排序的数组中找到给定元素的第一个和最后一个位置。 二分查找由于数组是有序的你可以使用二分查找来找到目标元素的索引。二分查找的基本思想是将数组分成两半比较中间元素与目标值然后根据比较结果决定是继续在左半部分查找还是右半部分查找。 找到第一个位置使用二分查找但需要稍作修改以找到第一个位置。在每次迭代中如果中间元素等于目标值你不能立即返回这个位置因为可能还有更小的索引也是目标值。你需要向左半边继续查找。 找到最后一个位置同样使用二分查找但这次如果中间元素等于目标值你需要向右半边继续查找因为可能还有更大的索引也是目标值。 边界条件在查找过程中需要处理数组的边界条件确保不会访问数组之外的索引。 c demo
#include vector
#include iostream// 二分查找函数用于找到目标值的索引
int binarySearch(const std::vectorint nums, int target, bool findFirst) {int left 0, right nums.size() - 1, result -1;while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {result mid; // 记录找到的位置if (findFirst) {right mid - 1; // 向左查找第一个位置}else {left mid 1; // 向右查找最后一个位置}}else if (nums[mid] target) {left mid 1;}else {right mid - 1;}}return result;
}// 主函数用于找到元素的第一个和最后一个位置
std::vectorint findFirstAndLastPosition(const std::vectorint nums, int target) {int first binarySearch(nums, target, true); // 找到第一个位置int last binarySearch(nums, target, false); // 找到最后一个位置return { first, last };
}int main() {std::vectorint nums { 5, 7, 7, 8, 8, 10 };int target 8;std::vectorint positions findFirstAndLastPosition(nums, target);std::cout First position: positions[0] std::endl;std::cout Last position: positions[1] std::endl;return 0;
}输出结果 First position: 3 Last position: 4 代码仓库地址findFirstAndLastPosition
