Leetcode Java Find Minimum in Rotated Sorted Array II
업데이트:
문제
코드
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + ((right - left) / 2);
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
} else {
right--;
}
}
return nums[left];
}
}
결과
설명
- 이전 문제인 Find Minimum in Rotated Sorted Array와 비슷하게 주어진 배열 nums의 최소 값을 찾는 문제이다.
- 단, 이전 문제와는 달리 주어진 배열 nums에 중복된 값이 포함된다.
- 문제 풀이에 필요한 변수를 정의한다.
- left는 nums 배열의 시작 index로, 이진 탐색에 사용될 변수이다.
- right는 nums 배열의 마지막 index로, 이진 탐색에 사용될 변수이다.
- left가 right보다 작을 때 까지 반복하여 left에 배열의 최소값의 index를 넣어준다.
- 중앙값인 mid는 $left + frac{(right - left)}{2}$ 값으로 넣어 nums[mid]의 값과 nums[right]의 값을 비교한한다.
- nums[mid]의 값이 nums[right]의 값보다 클 경우, left에 $mid + 1$를 넣어 탐색 구간을 좁혀준다.
- nums[mid]의 값이 nums[right]의 값보다 작을 경우, right에 mid를 넣어 탐색 구간을 좁혀준다.
- nums[mid]의 값이 nums[right]의 값과 같은 경우, right를 감소시켜 중복된 값을 무시한다.
- 중앙값인 mid는 $left + frac{(right - left)}{2}$ 값으로 넣어 nums[mid]의 값과 nums[right]의 값을 비교한한다.
- 반복이 완료되면 오름차순 정렬을 수행했을 경우 최소값이 되는 nums[left]의 값을 주어진 문제의 결과로 반환한다.
소스
Sample Code는 여기에서 확인 가능합니다.
댓글남기기