Search in Rotated Sorted Array II – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).
Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].
Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.
You must decrease the overall operation steps as much as possible.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0 Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3 Output: false
Constraints:
1 <= nums.length <= 5000-104 <= nums[i] <= 104numsis guaranteed to be rotated at some pivot.-104 <= target <= 104
C++ Search in Rotated Sorted Array II LeetCode Solution
class Solution {
public:
bool search(vector<int>& nums, int target) {
int left = 0, right = nums.size()-1, mid;
while(left<=right)
{
mid = (left + right) >> 1;
if(nums[mid] == target) return true;
// the only difference from the first one, trickly case, just updat left and right
if( (nums[left] == nums[mid]) && (nums[right] == nums[mid]) ) {++left; --right;}
else if(nums[left] <= nums[mid])
{
if( (nums[left]<=target) && (nums[mid] > target) ) right = mid-1;
else left = mid + 1;
}
else
{
if((nums[mid] < target) && (nums[right] >= target) ) left = mid+1;
else right = mid-1;
}
}
return false;
}
Java Search in Rotated Sorted Array II LeetCode Solution
public boolean search(int[] nums, int target) {
int start = 0, end = nums.length - 1, mid = -1;
while(start <= end) {
mid = (start + end) / 2;
if (nums[mid] == target) {
return true;
}
//If we know for sure right side is sorted or left side is unsorted
if (nums[mid] < nums[end] || nums[mid] < nums[start]) {
if (target > nums[mid] && target <= nums[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
//If we know for sure left side is sorted or right side is unsorted
} else if (nums[mid] > nums[start] || nums[mid] > nums[end]) {
if (target < nums[mid] && target >= nums[start]) {
end = mid - 1;
} else {
start = mid + 1;
}
//If we get here, that means nums[start] == nums[mid] == nums[end], then shifting out
//any of the two sides won't change the result but can help remove duplicate from
//consideration, here we just use end-- but left++ works too
} else {
end--;
}
}
return false;
}
Python 3 Search in Rotated Sorted Array II LeetCode Solution
def search(self, nums, target):
l, r = 0, len(nums)-1
while l <= r:
mid = l + (r-l)//2
if nums[mid] == target:
return True
while l < mid and nums[l] == nums[mid]: # tricky part
l += 1
# the first half is ordered
if nums[l] <= nums[mid]:
# target is in the first half
if nums[l] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
# the second half is ordered
else:
# target is in the second half
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
return False
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below
Related posts:
Search in Rotated Sorted Array – LeetCode Solution
Remove Duplicates from Sorted Array – LeetCode Solution
Find First and Last Position of Element in Sorted Array – LeetCode Solution
Remove Duplicates from Sorted Array II – LeetCode Solution
Search Insert Position – LeetCode Solution
Search a 2D Matrix – LeetCode Solution
