Package g0001_0100.s0081_search_in_rotated_sorted_array_ii

Class Solution

java.lang.Object

g0001_0100.s0081_search_in_rotated_sorted_array_ii.Solution

public class Solution
extends Object

81 - Search in Rotated Sorted Array II.<p>Medium</p> <p>There is an integer array <code>nums</code> sorted in non-decreasing order (not necessarily with <strong>distinct</strong> values).</p> <p>Before being passed to your function, <code>nums</code> is <strong>rotated</strong> at an unknown pivot index <code>k</code> (<code>0 <= k < nums.length</code>) such that the resulting array is <code>[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]</code> ( <strong>0-indexed</strong> ). For example, <code>[0,1,2,4,4,4,5,6,6,7]</code> might be rotated at pivot index <code>5</code> and become <code>[4,5,6,6,7,0,1,2,4,4]</code>.</p> <p>Given the array <code>nums</code> <strong>after</strong> the rotation and an integer <code>target</code>, return <code>true</code> <em>if</em> <code>target</code> <em>is in</em> <code>nums</code><em>, or</em> <code>false</code> <em>if it is not in</em> <code>nums</code><em>.</em></p> <p>You must decrease the overall operation steps as much as possible.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> nums = [2,5,6,0,0,1,2], target = 0</p> <p><strong>Output:</strong> true</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> nums = [2,5,6,0,0,1,2], target = 3</p> <p><strong>Output:</strong> false</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= nums.length <= 5000</code></li> <li><code>-10⁴ <= nums[i] <= 10⁴</code></li> <li><code>nums</code> is guaranteed to be rotated at some pivot.</li> <li><code>-10⁴ <= target <= 10⁴</code></li> </ul> <p><strong>Follow up:</strong> This problem is similar to <a href="https://github.com/javadev/LeetCode-in-Java/tree/main/src/main/java/g0001_0100/s0033_search_in_rotated_sorted_array/" target="_top">Search in Rotated Sorted Array</a>, but <code>nums</code> may contain <strong>duplicates</strong>. Would this affect the runtime complexity? How and why?</p>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
boolean	search(int[] nums, int target)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

search

public boolean search(int[] nums,
 int target)