-
[75 LeetCode] 36 - Search in Rotated Sorted ArrayStudy/Leetcode 2023. 5. 25. 19:50
[75 LeetCode]는 코딩테스트 연습을 위해 한 페이스북 개발자가 추천하는 75가지 알고리즘 문제를 풀어보는 시리즈이다.
블라인드 원문:
https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU문제 링크: https://leetcode.com/problems/search-in-rotated-sorted-array/submissions/957017518/
LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
이전에 풀었던 Find minimum in rotated sorted Array와 유사하다.
1. 섞였는지 안섞였는지 판단한다.
1. 만약 섞였다면 섞인 지점을 찾는다.
2. target이 첫 숫자보다 크거나 같으면 크면 섞인 곳으로부터 왼쪽, 그렇지 않은 경우 오른쪽에 속한다.
2. l과 r을 구간에 맞게 설정해준다.
3. 이진탐색으로 target을 찾는다.
4. 못찾으면 -1을 리턴한다.var search = function(nums, target) { let l = 0, r = nums.length; let leftBound = 0; let ans = -1; let mid = 0; const isRotated = nums[0] > nums[nums.length - 1]; if (isRotated) { while (l < r) { mid = Math.floor((l + r) / 2); if (nums[mid] === target) return mid; if (nums[mid] > nums[nums.length - 1]) { l = mid + 1; } else { r = mid; } } leftBound = l; if (target >= nums[0]) { l = 0; r = leftBound; } else { l = leftBound; r = nums.length; } } while (l < r) { mid = Math.floor((l + r) / 2); if (nums[mid] < target) { l = mid + 1; } else { r = mid; } } if (nums[l] === target) ans = l; return ans; };
728x90'Study > Leetcode' 카테고리의 다른 글
[75 LeetCode] 38 - Word Break (3) 2023.05.28 [75 LeetCode] 37 - Reverse Bits (0) 2023.05.25 [75 LeetCode] 35 - Container With Most Water (0) 2023.05.25 [75 LeetCode] 34 - 3 Sum (0) 2023.05.22 [75 LeetCode] 33 - Missing Number (0) 2023.05.13