81. 회전 정렬된 배열에서 검색 II
설명
내림차순으로 정렬된 정수 배열nums이 있습니다(반드시 고유한 값이 있는 것은 아님).
함수에 전달되기 전에 nums는 결과 배열이 k (0-인덱싱됨)이 되도록 알 수 없는 피벗 인덱스 0 <= k < nums.length ( [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] )에서 회전됩니다. 예를 들어 [0,1,2,4,4,4,5,6,6,7]는 피벗 인덱스5에서 회전하여 [4,5,6,6,7,0,1,2,4,4]가 될 수 있습니다.
회전 후 배열nums과 정수target가 주어지면 true가 target에 있는 경우 nums를 반환하거나 (4)6에 없는 경우 false를 반환합니다.
전체 작업 단계를 최대한 줄여야 합니다.
예 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
예 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
제약:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
nums 1 <= nums.length <= 5000 104 <= nums[i] <= 104 어떤 피벗에서 회전하도록 보장됩니다. nums 솔루션
솔루션 1
직관
그냥 정렬된 부분에 들어가
암호
class Solution {
public boolean search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
while (l < r && nums[l] == nums[l + 1]) {
l++;
}
while (l < r && nums[r] == nums[r - 1]) {
r--;
}
int mid = l + r >> 1;
if (nums[mid] == target) {
return true;
}
if (nums[l] <= nums[mid]) {
if (nums[l] <= target && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[r]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return false;
}
}
복잡성
class Solution {
public boolean search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
while (l < r && nums[l] == nums[l + 1]) {
l++;
}
while (l < r && nums[r] == nums[r - 1]) {
r--;
}
int mid = l + r >> 1;
if (nums[mid] == target) {
return true;
}
if (nums[l] <= nums[mid]) {
if (nums[l] <= target && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[r]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return false;
}
}
Reference
이 문제에 관하여(81. 회전 정렬된 배열에서 검색 II), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/jiangwenqi/81-search-in-rotated-sorted-array-ii-14en텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
