优秀设计网站点评,网站设计方案图,淘宝店铺代运营一般怎么收费,个人网站的制作步骤前言
数组类型题目练习。 练习题 七【34. 在排序数组中查找元素的第一个和最后一个位置】 一、题目阅读
给你一个按照非递减顺序排列的整数数组 nums#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target和一个目标值 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] 109
nums 是一个非递减数组
-109 target 109二、尝试实现
思路
理解题目nums从小到大已经排好顺序第一个问题找target在不在第二个问题返回target下标的开始和结束。直观用遍历nums一遍但是时间复杂度O(n)。题目不让用。pass找一个元素在不在集合里可以想到哈希法。可是选择什么结构用数组还是要遍历nums只是统计次数用无序的unordered_set或者map感觉都不好用放次数还是放下标还是得遍历nums时间复杂度没降低。二分查找因为nums排好序可以直接用。如果找到target逐步缩小区间就可以确定位置。nice。时间复杂度是O(log n)。
代码实现
测试通过。
class Solution {
public:vectorint searchRange(vectorint nums, int target) {vectorint result;int left 0;int right nums.size()-1;while(left right){int middle (left right)/2;if(nums[middle] target){left middle 1;}else if(nums[middle] target){right middle -1;}else if(nums[middle] target){while(nums[left] target){left;}while(nums[right] target){right--;}result.push_back(left);result.push_back(right);break;}}if(result.empty()){result {-1,-1};}return result;}
};三、参考答案
参考答案链接
学习内容
1左右边界分别来找也是用二分法可是在找边界的时候什么时候动left和right有点绕还是。 2找右边界
如果middle的值比target大肯定在[left,middle-1]之间所以只把right middle-1;若middle的值小于等于target肯定在[middle1,right]之间所以left middle1;还要rightboard left;为什么rightboard在else条件下还要始终跟着left走如果不走会怎么样最后直接return left
3找左边界
如果middle的值比target大肯定在[left,middle-1]之间所以只把right middle-1;若middle的值小于等于target肯定在[middle1,right]之间所以left middle1;还要rightboard left;为什么leftboard在else条件下还要始终跟着right走如果不走会怎么样最后直接return right 总结
选择个人方法使用二分查找如果找到target就逐步缩小两端。 参考思路还需要去注意找右边界是小于等于调整找左边界是大于等于调整。不如个人方法。
欢迎指正转载标明出处
