leetcode Find First and Last Position of Element in Sorted Array問題解
1592 ワード
タイトルの説明:
Given an array of integers
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return
Example 1:
Example 2:
日本語の理解:
増分されたシーケンスとターゲット値が与えられ、シーケンスにターゲット値がある場合、その値の下付きの開始値と終了値が返されます.
問題解決の考え方:
まず、このtarget値の配列中の存在下標を探し出し、二分法を用いて検索し、時間複雑度がlog(n)であり、その下標を返し、その後、この下標を起止値とし、左右に遍歴し、配列値がtargetと同じように遍歴を続けなければ、終了し、その値が配列中に存在する開始下標を得ることができる.
コード(java):
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]日本語の理解:
増分されたシーケンスとターゲット値が与えられ、シーケンスにターゲット値がある場合、その値の下付きの開始値と終了値が返されます.
問題解決の考え方:
まず、このtarget値の配列中の存在下標を探し出し、二分法を用いて検索し、時間複雑度がlog(n)であり、その下標を返し、その後、この下標を起止値とし、左右に遍歴し、配列値がtargetと同じように遍歴を続けなければ、終了し、その値が配列中に存在する開始下標を得ることができる.
コード(java):
class Solution {
public int[] searchRange(int[] nums, int target) {
int []res={-1,-1};
int result=seach(nums,target);
if(result==-1)return res;
else{
int start=result-1,end=result+1;
while(start>=0){
if(nums[start]==target)start--;
else break;
}
while(endtarget){
end=mid-1;
}
else if(nums[mid]