(Leetcode) 33 - Search in Rotated Sorted Array
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
https://leetcode.com/problems/search-in-rotated-sorted-array/
내가 작성한 풀이
값을 발견하면 index를 반환하고, 아닐경우 -1을 반환한다.
class Solution {
public int search(int[] nums, int target) {
for(int i = 0 ; i < nums.length; i++) {
if(nums[i] == target) {
return i;
}
}
return -1;
}
}
TC, SC
시간 복잡도는 O(n)이고, 공간 복잡도는 O(1)이다.
조금 더 최적화 하자면 (binary search)
문제에서 O(log n) 의 시간복잡도로 풀어보라고 제시하였다.
(Leetcode) 153 - Find Minimum in Rotated Sorted Array 바로 이전에 풀었던 문제와 비슷하게 접근하면 될 것으로 보인다.
- right가 mid보다 크다? → 오른쪽 부분은 제대로 정렬되어 있다
- right가 mid보다 작다? → 왼쪽 부분은 제대로 정렬되어 있다.
이 두가지를 이용하면 된다.
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if(nums[mid] < nums[right]) {
if (target < nums[mid] || target > nums[right]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (target < nums[left] || target > nums[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
TC, SC
시간 복잡도는 O(logn)이고, 공간 복잡도는 O(1)이다.