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] <= 104
nums
is 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