✏️
leetcode solution
  • Leetcode Solutions
  • LeetCode 1. Two Sum
  • LeetCode 2. Add Two Numbers
  • LeetCode 3. Longest Substring Without Repeating Characters
  • LeetCode 4. Median of Two Sorted Arrays
  • LeetCode 5. Longest Palindromic Substring
  • LeetCode 6. ZigZag Conversion
  • LeetCode 7. Reverse Integer
  • LeetCode 8. String to Integer (atoi)
  • LeetCode 9. Palindrome Number
  • LeetCode 10. Regular Expression Matching
  • LeetCode 11. Container With Most Water
  • LeetCode 12. Integer to Roman
  • LeetCode 13. Roman to Integer
  • LeetCode 14. Longest Common Prefix
  • LeetCode 15. 3Sum
  • LeetCode 16. 3Sum Closest
  • LeetCode 17. Letter Combinations of a Phone Number
  • LeetCode 18. 4Sum
  • LeetCode 19. Remove Nth Node From End of List
  • LeetCode 20. Valid Parentheses
  • LeetCode 21. Merge Two Sorted Lists
  • LeetCode 22. Generate Parentheses
  • LeetCode 23. Merge k Sorted Lists
  • LeetCode 24. Swap Nodes in Pairs
  • LeetCode 25. Reverse Nodes in k-Group
  • LeetCode 26. Remove Duplicates from Sorted Array
  • LeetCode 27. Remove Element
  • LeetCode 28. Implement strStr()
  • LeetCode 29. Divide Two Integers
  • LeetCode 30. Substring with Concatenation of All Words
  • LeetCode 31. Next Permutation
  • LeetCode 32. Longest Valid Parentheses
  • LeetCode 33. Search in Rotated Sorted Array
  • LeetCode 42. Trapping Rain Water
  • LeetCode 56. Merge Intervals
  • LeetCode 67. Add Binary
  • LeetCode 81. Search in Rotated Sorted Array II
  • LeetCode 124. Binary Tree Maximum Path Sum
  • LeetCode 125. Valid Palindrome
  • LeetCode 153. Find Minimum in Rotated Sorted Array
  • LeetCode 154. Find Minimum in Rotated Sorted Array II
  • LeetCode 157. Read N Characters Given Read4
  • LeetCode 158. Read N Characters Given Read4 II - Call multiple times
  • LeetCode 236. Lowest Common Ancestor of a Binary Tree
  • LeetCode 238. Product of Array Except Self
  • LeetCode 269. Alien Dictionary
  • Leetcode 295. Find Median from Data Stream
  • Leetcode 297. Serialize and Deserialize Binary Tree
  • LeetCode 300. Longest Increasing Subsequence
  • LeetCode 301. Remove Invalid Parentheses
  • LeetCode 336. Palindrome Pairs
  • LeetCode 407. Trapping Rain Water II
  • LeetCode 415. Add Strings
  • LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List
  • LeetCode 489. Robot Room Cleaner
  • LeetCode 560. Subarray Sum Equals K
  • LeetCode 680. Valid Palindrome II
  • LeetCode 710. Random Pick with Blacklist
  • LeetCode 721. Accounts Merge
  • LeetCode 863. All Nodes Distance K in Binary Tree
  • LeetCode 918. Maximum Sum Circular Subarray
  • LeetCode 953. Verifying an Alien Dictionary
  • LeetCode 973. K Closest Points to Origin
  • LeetCode 1249. Minimum Remove to Make Valid Parentheses
  • LeetCode 1428. Leftmost Column with at Least a One
  • LeetCode 1570. Dot Product of Two Sparse Vectors
  • LeetCode 1644. Lowest Common Ancestor of a Binary Tree II
  • LeetCode 1650. Lowest Common Ancestor of a Binary Tree III
  • LeetCode 1676. Lowest Common Ancestor of a Binary Tree IV
  • Leetcode 1727. Largest Submatrix With Rearrangements
  • LeetCode 1751. Maximum Number of Events That Can Be Attended II
  • LeetCode 1754. Largest Merge Of Two Strings
  • LeetCode 1755. Closest Subsequence Sum
  • LeetCode 1760. Minimum Limit of Balls in a Bag
  • LeetCode 1761. Minimum Degree of a Connected Trio in a Graph
  • LeetCode 1764. Form Array by Concatenating Subarrays of Another Array
  • LeetCode 1765. Map of Highest Peak
  • LeetCode 1766. Tree of Coprimes
  • LeetCode 1770. Maximum Score from Performing Multiplication Operations
  • LeetCode 1771. Maximize Palindrome Length From Subsequences
  • LeetCode 1774. Closest Dessert Cost
  • LeetCode. 1775 Equal Sum Arrays With Minimum Number of Operations
  • LeetCode 1776. Car Fleet II
  • LeetCode 1778. Shortest Path in a Hidden Grid
  • LeetCode 1779. Find Nearest Point That Has the Same X or Y Coordinate
  • LeetCode 1780. Check if Number is a Sum of Powers of Three
  • LeetCode 1781. Sum of Beauty of All Substrings
  • LeetCode 1782. Count Pairs Of Nodes
  • LeetCode 1784. Check if Binary String Has at Most One Segment of Ones
  • LeetCode 1785. Minimum Elements to Add to Form a Given Sum
  • LeetCode 1786. Number of Restricted Paths From First to Last Node
  • LeetCode 1787. Make the XOR of All Segments Equal to Zero
  • LeetCode 1788. Maximize the Beauty of the Garden
  • LeetCode 1790. Check if One String Swap Can Make Strings Equal
  • LeetCode 1791. Find Center of Star Graph
  • LeetCode 1792. Maximum Average Pass Ratio
  • LeetCode 1793. Maximum Score of a Good Subarray
  • LeetCode 1794. Count Pairs of Equal Substrings With Minimum Difference
  • LeetCode 1796. Second Largest Digit in a String
  • LeetCode 1797. Design Authentication Manager
  • LeetCode 1798. Maximum Number of Consecutive Values You Can Make
  • LeetCode 1799. Maximize Score After N Operations
  • LeetCode 1800. Maximum Ascending Subarray Sum
  • LeetCode 1801. Number of Orders in the Backlog
  • LeetCode 1802. Maximum Value at a Given Index in a Bounded Array
  • LeetCode 1803. Count Pairs With XOR in a Range
  • LeetCode 1804. Implement Trie II (Prefix Tree)
  • LeetCode 1805. Number of Different Integers in a String
  • LeetCode 1807. Evaluate the Bracket Pairs of a String
  • LeetCode 1808. Maximize Number of Nice Divisors
  • LeetCode 1810. Minimum Path Cost in a Hidden Grid
  • LeetCode 1812. Determine Color of a Chessboard Square
  • LeetCode 1813. Sentence Similarity III
  • LeetCode 1814. Count Nice Pairs in an Array
  • LeetCode 1815. Maximum Number of Groups Getting Fresh Donuts
  • LeetCode 1816. Truncate Sentence
  • LeetCode 1817. Finding the Users Active Minutes
  • LeetCode 1818. Minimum Absolute Sum Difference
  • LeetCode 1819. Number of Different Subsequences GCDs
  • LeetCode 1820. Maximum Number of Accepted Invitations
  • LeetCode 1822. Sign of the Product of an Array
  • LeetCode 1824. Minimum Sideway Jumps
  • LeetCode 1825. Finding MK Average
  • LeetCode 1826. Faulty Sensor
  • LeetCode 1827. Minimum Operations to Make the Array Increasing
  • LeetCode 1828. Queries on Number of Points Inside a Circle
  • LeetCode 1829. Maximum XOR for Each Query
  • LeetCode 1830. Minimum Number of Operations to Make String Sorted
  • LeetCode 1832. Check if the Sentence Is Pangram
  • LeetCode 1833. Maximum Ice Cream Bars
  • LeetCode 1834. Single-Threaded CPU
  • LeetCode 1835. Find XOR Sum of All Pairs Bitwise AND
  • LeetCode 1836. Remove Duplicates From an Unsorted Linked List
  • LeetCode 1837. Sum of Digits in Base K
  • LeetCode 1839. Longest Substring Of All Vowels in Order
  • LeetCode 1840. Maximum Building Height
  • LeetCode 1847. Closest Room
  • LeetCode 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number
  • LeetCode 1851. Minimum Interval to Include Each Query
Powered by GitBook
On this page

Was this helpful?

Last updated 4 years ago

Was this helpful?

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

  • [4,5,6,7,0,1,4] if it was rotated 4 times.

  • [0,1,4,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

Example 1:

Example 2:

Constraints:

  • n == nums.length

  • 1 <= n <= 5000

  • -5000 <= nums[i] <= 5000

  • nums is sorted and rotated between 1 and n times.

Follow up: This is the same as but with duplicates. Would allow duplicates affect the run-time complexity? How and why?

Solution

class Solution {
public:
    int findMin(vector<int>& nums) {
        int i = 0;
        int j = nums.size() - 1;
        
        while (i < j) {
            int mid = (i + j) / 2;
            if (nums[mid] < nums[j]) {
                j = mid;
            } else if (nums[mid] > nums[j]) {
                i = mid + 1;
            } else {
                j--;
            }
        }
        
        return nums[i];
    }
};

LeetCode 154. Find Minimum in Rotated Sorted Array II

Binary Search

PreviousLeetCode 153. Find Minimum in Rotated Sorted ArrayNextLeetCode 157. Read N Characters Given Read4
Input: nums = [1,3,5]
Output: 1
Input: nums = [2,2,2,0,1]
Output: 0
Find Minimum in Rotated Sorted Array
English Version in Youtube
中文版解答Youtube Link
中文版解答Bilibili Link