LeetCode - 회전 정렬 배열에서 검색 II
23453 단어 gojavascriptalgorithmsprogramming
문제 설명
감소하지 않는 순서로 정렬된 정수 배열 nums가 있습니다(반드시 고유한 값이 있는 것은 아님).
함수에 전달되기 전에 nums는 결과 배열이 [nums[k], nums[k + 1], ..., nums가 되도록 알 수 없는 피벗 인덱스 k(0 <= k < nums.length)에서 회전합니다. [n - 1], nums[0], nums[1], ..., nums[k - 1]] (인덱스 0). 예를 들어 [0, 1, 2, 4, 4, 4, 5, 6, 6, 7]은 피벗 인덱스 5에서 회전하여 [4, 5, 6, 6, 7, 0, 1, 2, 4, 4].
회전 후 배열 숫자와 정수 대상이 주어지면 대상이 숫자이면 true를 반환하고 숫자가 아니면 false를 반환합니다.
전체 작업 단계를 최대한 줄여야 합니다.
다음에서 가져온 문제 설명: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/ .
예 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
제약:
- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- 0 <= k <= 10^5
설명
이 문제에 대한 해결책은 이전 [Search in Rotated Sorted Array(https://alkeshghorpade.me/post/leetcode-search-in-rotated sorted-array)]와 유사합니다. 유일한 차이점은 중복이 있기 때문에 nums[low] == nums[mid]가 가능성이 있으며 이 경우를 별도로 처리해야 한다는 것입니다.
알고리즘으로 직접 이동해 보겠습니다.
// search function
- if low > high
- return -1
- set mid = low + (high - low) / 2
- if nums[mid] == key
- return true
- if nums[low] == nums[mid + 1] && nums[high] == nums[mid]
- low++
- high--
- search(nums, low, high, key)
if nums[low] <= nums[mid]
- if key >= nums[low] && key <= nums[mid]
- return search(nums, low, mid - 1, key)
- return search(nums, mid + 1, high, key)
if key >= nums[mid] && key <= nums[high]
- return search(nums, mid + 1, high, key)
- return search(nums, low, mid - 1, key)
C++, Golang 및 Javascript의 솔루션을 확인해 봅시다.
C++ 솔루션
class Solution {
public:
bool searchUtil(vector<int>& nums, int low, int high, int target) {
if(low > high) {
return false;
}
int mid = low + (high - low)/2;
if(nums[mid] == target){
return true;
}
if(nums[low] == nums[mid] && nums[high] == nums[mid]){
low++;
high--;
return searchUtil(nums, low, high, target);
}
if(nums[low] <= nums[mid]){
if(target >= nums[low] && target <= nums[mid]){
return searchUtil(nums, low, mid - 1, target);
}
return searchUtil(nums, mid + 1, high, target);
}
if(target >= nums[mid] && target <= nums[high]){
return searchUtil(nums, mid + 1, high, target);
}
return searchUtil(nums, low, mid - 1, target);
}
bool search(vector<int>& nums, int target) {
bool result = searchUtil(nums, 0, nums.size() - 1, target);
return result;
}
};
골랑 솔루션
func searchUtil(nums []int, low, high, target int) bool {
if low > high {
return false
}
mid := low + (high - low) / 2
if nums[mid] == target {
return true
}
if nums[low] == nums[mid] && nums[high] == nums[mid] {
low++
high--
return searchUtil(nums, low, high, target)
}
if nums[low] <= nums[mid] {
if target >= nums[low] && target <= nums[mid] {
return searchUtil(nums, low, mid - 1, target)
}
return searchUtil(nums, mid + 1, high, target)
}
if target >= nums[mid] && target <= nums[high] {
return searchUtil(nums, mid + 1, high, target);
}
return searchUtil(nums, low, mid - 1, target);
}
func search(nums []int, target int) bool {
return searchUtil(nums, 0, len(nums) - 1, target)
}
자바스크립트 솔루션
var searchUtil = function(nums, low, high, target) {
if(low > high) {
return false;
}
let mid = low + (high - low)/2;
if(nums[mid] == target){
return true;
}
if(nums[low] == nums[mid] && nums[high] == nums[mid]){
low++;
high--;
return searchUtil(nums, low, high, target);
}
if(nums[low] <= nums[mid]){
if(target >= nums[low] && target <= nums[mid]){
return searchUtil(nums, low, mid - 1, target);
}
return searchUtil(nums, mid + 1, high, target);
}
if(target >= nums[mid] && target <= nums[high]){
return searchUtil(nums, mid + 1, high, target);
}
return searchUtil(nums, low, mid - 1, target);
};
var search = function(nums, target) {
return searchUtil(nums, 0, nums.length - 1, target);
};
문제를 연습해 봅시다.
Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 3
// search function
Step 1: searchUtil(nums, 0, nums.size() - 1, target)
searchUtil(nums, 0, 6, 0)
// searchUtil function
Step 2: low > high
0 > 6
false
Step 3: mid = low + (high - low)/2
= 0 + (6 - 0)/2
= 0 + 6/2
= 3
Step 4: if nums[mid] == target
nums[3] == 3
0 == 3
false
Step 5: if nums[low] == nums[mid] && nums[high] == nums[mid]
nums[0] == nums[3] && nums[6] == nums[3]
2 == 0 && 2 == 0
false
Step 6: if nums[low] <= nums[mid]
nums[0] <= nums[3]
2 <= 0
false
Step 7: if target >= nums[mid] && target <= nums[high]
3 >= nums[3] && 3 <= nums[6]
3 >= 0 && 3 <= 2
false
Step 8: searchUtil(nums, low, mid - 1, target)
searchUtil(nums, 0, 2, 3)
// searchUtil function
Step 9: low > high
0 > 2
false
Step 10: mid = low + (high - low)/2
= 0 + (2 - 0)/2
= 0 + 2/2
= 1
Step 11: if nums[mid] == target
nums[1] == 3
5 == 3
false
Step 12: if nums[low] == nums[mid] && nums[high] == nums[mid]
nums[0] == nums[1] && nums[2] == nums[1]
2 == 5 && 6 == 5
false
Step 13: if nums[low] <= nums[mid]
nums[0] <= nums[1]
2 <= 5
true
if target >= nums[low] && target <= nums[mid]
3 >= nums[0] && 3 <= nums[1]
3 >= 2 && 3 <= 5
true
return searchUtil(nums, low, mid - 1, target)
searchUtil(nums, 0, 1 - 1, 3)
searchUtil(nums, 0, 0, 3)
// searchUtil function
Step 14: if low > high
0 > 0
false
Step 15: mid = low + (high - low)/2
= 0 + (0 - 0)/2
= 0 + 0/2
= 0
Step 16: if nums[mid] == target
nums[0] == 3
2 == 3
false
Step 17: if nums[low] == nums[mid] && nums[high] == nums[mid]
nums[0] == nums[0] && nums[0] == nums[0]
2 == 2 && 2 == 2
true
low++
low = 1
high--
high = -1
return searchUtil(nums, low, high, target)
searchUtil(nums, 1, -1, 3)
// searchUtil function
Step 14: if low > high
1 > -1
true
return false
// We go back from Step 14 to Step 9 to Step 2 to Step 1 because of recursion
We return the answer as false.
Reference
이 문제에 관하여(LeetCode - 회전 정렬 배열에서 검색 II), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/_alkesh26/leetcode-search-in-rotated-sorted-array-ii-22b5텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)