本文将为您提供关于leetcode个人题解——#34FindFirstandLastPositionofElementinSortedArray的详细介绍，我们还将为您解释leetcode1的相关知识
本文将为您提供关于leetcode个人题解——#34 Find First and Last Position of Element in Sorted Array的详细介绍，我们还将为您解释leetcode1的相关知识，同时，我们还将为您提供关于19.2.2 [LeetCode 34] Find First and Last Position of Element in Sorted Array、34 Find First and Last Position of Element in Sorted Array、34. Find First and Last Position of Element in Sorted Array、34. Find First and Last Position of Element in Sorted Array （JAVA)的实用信息。
本文目录一览：- leetcode个人题解——#34 Find First and Last Position of Element in Sorted Array（leetcode1）
- 19.2.2 [LeetCode 34] Find First and Last Position of Element in Sorted Array
- 34 Find First and Last Position of Element in Sorted Array
- 34. Find First and Last Position of Element in Sorted Array
- 34. Find First and Last Position of Element in Sorted Array （JAVA)
leetcode个人题解——#34 Find First and Last Position of Element in Sorted Array（leetcode1）
思路：先二分查找到一个和target相同的元素，然后再左边二分查找左边界，右边二分查找有边界。
class Solution { public: int begin = -1,end = -1; int ends; int lSearch(int left,int right,vector<int>& nums,int target) { if(left > right) return -1; int mid = (left + right) / 2; if(nums[mid] == target){ if(mid == 0 || (mid > 0 && nums[mid - 1] < target)) return mid; else return lSearch(left,mid - 1,nums,target); }else return lSearch(mid + 1,right,target); return -1; } int rSearch(int left,int target) { if(left > right) return -1; int mid = (left + right) / 2; if(nums[mid] == target){ if(mid == ends || (mid < ends && nums[mid + 1] > target)) return mid; else return rSearch(mid + 1,target); }else return rSearch(left,target); return -1; } int midSearch(int left,int target) { if(left > right) return -1; int mid = (left + right) / 2; if(nums[mid] == target){ return mid; } else if(nums[mid] < target) return midSearch(mid + 1,target); else if(nums[mid] > target) return midSearch(left,target); return -1; } vector<int> searchRange(vector<int>& nums,int target) { ends = nums.size() - 1; int mid = midSearch(0,ends,target); if(mid != -1){ begin = lSearch(0,mid,target); end = rSearch(mid,target); } vector<int> ans; ans.push_back(begin); ans.push_back(end); return ans; } };
![19.2.2 [LeetCode 34] Find First and Last Position of Element in Sorted Array](http://www.gvkun.com/zb_users/upload/2025/02/6ab0195d-11e0-4578-9bb8-6d834a0df4131739342691254.jpg "19.2.2 [LeetCode 34] Find First and Last Position of Element in Sorted Array")
19.2.2 [LeetCode 34] Find First and Last Position of Element in Sorted Array
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 = [,target = 8
Output: [3,4]5,7,8,10]
Example 2:
Input: nums = [,target = 6
Output: [-1,-1]5,10]
题意
找已排序数组中某个值的范围
题解
1 class Solution { 2 public: 3 vector<int> searchRange(vector<int>& nums,int target) { 4 int size = nums.size(),s = 0,e = size - 1; 5 vector<int>ans; 6 if (size <= 0||target<nums[0]||target>nums[size-1]) { 7 ans.push_back(-1); 8 ans.push_back(-1); 9 return ans; 10 } 11 while (s < e) { 12 int mid = (s + e) / 2; 13 if (nums[mid] < target) 14 s = mid + 1; 15 else 16 e = mid; 17 } 18 if (nums[s] != target) { 19 ans.push_back(-1); 20 ans.push_back(-1); 21 return ans; 22 } 23 ans.push_back(s); 24 s = 0,e = size - 1; 25 while (s <= e) { 26 int mid = (s + e) / 2; 27 if (nums[mid] <= target) 28 s = mid + 1; 29 else 30 e = mid - 1; 31 } 32 ans.push_back(e); 33 return ans; 34 } 35 };
两次二分
34 Find First and Last Position of Element in Sorted Array
自己写的， accepted
class Solution {
public int[] searchRange(int[] nums, int target) {
// sanity check
if(nums == null || nums.length == 0) return new int[]{-1, -1};
int[] res = new int[2];
res[0] = first(nums, target);
res[1] = last(nums, target);
return res;
}
private int first(int[] nums, int target){
int left = 0;
int right = nums.length - 1;
while(left < right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){
right = mid;
}else if(nums[mid] < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
if(nums[left] != target) return -1;
return left;
}
private int last(int[] nums, int target){
int left = 0;
int right = nums.length - 1;
while(left < right - 1){
int mid = left + (right - left) / 2;
if(nums[mid] == target){
left = mid;
}else if(nums[mid] < target){
left = mid + 1;
}else{
right = mid;
}
}
// post processing
if(nums[right] == target) return right;
if(nums[left] == target) return left;
return -1;
}
}这个也是， 得自己走例子， 才知道什么时候需要post processing , 什么时候不需要， 这个题一个问不需要， 第二问就需要了
所以不要背答案， 要真的理解， 自己走例子
Given an array of integersnumssorted in ascending order, find the starting and ending position of a giventargetvalue.
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]
34. Find First and Last Position of Element in Sorted Array
1. 原始题目
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1]
2. 思路
既然是有序数组，可以 2 分法。如果存在该元素，那么跳出循环后肯定满足 nums [mid]==target ! 否则不存在该元素。
找到该元素后，两个指针分别向左，右移，寻找其初始和结尾位置即可。
3. 解题
1 class Solution:
2 def searchRange(self, nums: List[int], target: int) -> List[int]:
3 if not nums:return[-1,-1]
4 low, high = 0,len(nums)-1
5 while(low<=high): # 二分法
6 mid = int((low+high)/2)
7 if nums[mid]==target:
8 break
9 elif nums[mid]<target:
10 low = mid+1
11 else:
12 high=mid-1
13 results = [-1,-1]
14 print(mid)
15 if low<=high and nums[mid]==target: # 这句话判断是否找到了该元素。low<=high是必须的，否则就不存在该元素
16 i,j = mid,mid # 左右指针
17 while(i>=1 and nums[i-1]==target):i-=1
18 while(j<len(nums)-1 and nums[j+1]==target):j+=1
19 results = [i,j]
20 return results
21
34. Find First and Last Position of Element in Sorted Array （JAVA)
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given targetvalue.
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]
用二分法分别查找最左位置 和最有位置。
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ret = new int[2];
ret[0] = binaryLeftSearch(nums,target,0,nums.length-1);
ret[1] = binaryRightSearch(nums,target,0,nums.length-1);
return ret;
}
public int binaryLeftSearch(int[] nums, int target, int left, int right){
if(left > right) return -1;
int mid = left + ((right-left)>>1);
int mostLeft;
if(target <= nums[mid]) {
mostLeft = binaryLeftSearch(nums,target,left,mid-1);
if(mostLeft == -1 && target==nums[mid]) mostLeft = mid;
}
else{ //target > nums[mid]
mostLeft = binaryLeftSearch(nums,target,mid+1,right);
}
return mostLeft;
}
public int binaryRightSearch(int[] nums, int target, int left, int right){
if(left > right) return -1;
int mid = left + ((right-left)>>1);
int mostRight;
if(target >= nums[mid]) {
mostRight = binaryRightSearch(nums,target,mid+1,right);
if(mostRight == -1 && target==nums[mid]) mostRight = mid;
}
else{ //target < nums[mid]
mostRight = binaryRightSearch(nums,target,left,mid-1);
}
return mostRight;
}
}
我们今天的关于leetcode个人题解——#34 Find First and Last Position of Element in Sorted Array和leetcode1的分享已经告一段落，感谢您的关注，如果您想了解更多关于19.2.2 [LeetCode 34] Find First and Last Position of Element in Sorted Array、34 Find First and Last Position of Element in Sorted Array、34. Find First and Last Position of Element in Sorted Array、34. Find First and Last Position of Element in Sorted Array （JAVA)的相关信息，请在本站查询。
本文标签：
