【LeetCode】【找元素】Find First and Last Position of Element in Sorted Array
2024-09-07 20:11:10
描述：
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
思路一：一次Binary Search
先使用二分查找找到和taget相等的起始位置的元素，然后在这个位置向两边扩散找到值相同的范围。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res(,-);
if(nums.size() == ) return res;
int cau = dichotomy(nums,target);
if(cau == -) return res;
else{
int i = cau,j = cau;
cout<<cau<<endl;
while((i>= && nums[i] == target) || (j<=nums.size()- && nums[j] == target)){
if(i>= && nums[i] == target){
res[] = i;
cout<<i<<endl;
i--;
}
if(j<=nums.size()- && nums[j] == target){
res[] = j;
cout<<j<<endl;
j++;
}
}
}
return res;
}
int dichotomy(vector<int>& nums, int target){
int low = ,int high = nums.size() - ;
while(low < high){
int mid = (low + high + ) / ;
if(nums[mid] == target) return mid;
if(nums[mid] < target) low = mid + ;
else high = mid - ;
}
return -;
}
};
思路二：两3次Binary Search
先根据上述的二分查找，找到起始位置的元素，然后从low开始继续使用一次二分查找找到target+1的位置，然后返回这个位置it - 1，从而找到起始和终止的范围。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res(,-);
if(nums.size() == ) return res;
int low = dichotomy(nums,target,); //找起始元素
cout<<low<<endl;
if(low == nums.size() || nums[low] != target) //可能出现到数组结尾还是target比low处元素大，low=nums.size
return res;
else{
res[] = low;
res[] = dichotomy(nums,target+,low) - ; //找结尾元素
}
return res;
}
int dichotomy(vector<int>& nums, int target, int low){
int high = nums.size(); //核心
while(low < high){
int mid = (low + high ) / ;
if(nums[mid] < target) low = mid + ;
else high = mid;
}
return low;
}
};
最新文章
- java Io流输出指定文件的内容
- SpringMVC 对比 struts2
- “不是有效WIN32程序”
- Spring中的设计模式学习
- 转！！！Mybatis实现数据的增删改查（CRUD）
- 13test05：亲密数
- webhdfs追加写HDFS异常
- C#中用JavaScriptSerializer和Json.Net操作json格式的文件
- 用JS实现回文数的精准辨别！！！
- 搭建 Android 开发环境，初试HelloWorld (win7) （下） （转）
- bzoj1059: [ZJOI2007]矩阵游戏
- Day10 网络编程（续）
- Qt4项目迁移到Qt5问题：greaterThan(QT_MAJOR_VERSION, 4): QT += widgets .
- Docker最全教程之Python爬网实战(二十一)
- Mysql七种 JOIN 连接
- TS学习随笔（三)->接口
- <数据结构基础学习>（二）简单的时间复杂度分析
- Mysql SQL注入漏洞
- POJ 1064 1759 3484 3061 (二分搜索)
- JGraphT