[leetcode] 34. 정렬 배열 에서 요소 의 첫 번 째 와 마지막 위 치 를 찾 습 니 다 (2 분 찾기)
7558 단어 leetcode
당신 의 알고리즘 시간 복잡 도 는 반드시 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]
링크:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
사고 2: 2 분 에 찾 아 왼쪽 과 오른쪽 두 개의 경 계 를 찾 습 니 다.코드 참조 리 뷰 영역
// https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
// 34.
// O(log n)
vector<int> searchRange(vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
int res = -1;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (nums[mid] == target)
{
res = mid;
l = mid;
r = mid;
break;
}
if (nums[mid] < target) l = mid + 1;
if (nums[mid] > target) r = mid - 1;
}
if (res == -1)
{
return vector<int>{-1, -1};
}
else
{
for (int i = res-1; i >= 0; i--)
{
if (nums[i] == target)
{
l = i;
}
}
for (int i = res + 1; i < nums.size(); i++)
{
if (nums[i] == target)
{
r = i;
}
}
}
return vector<int>{l, r};
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.