C++实现LeetCode(154.寻找旋转有序数组的最小值之二)

[LeetCode] 154. Find Minimum in Rotated Sorted Array II 寻找旋转有序数组的最小值之二

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:

Input: [1,3,5]
Output: 1

Example 2:

Input: [2,2,2,0,1]
Output: 0

Note:

  • This is a follow up problem to Find Minimum in Rotated Sorted Array.
  • Would allow duplicates affect the run-time complexity? How and why?

这道寻找旋转有序重复数组的最小值是之前那道 Find Minimum in Rotated Sorted Array 的拓展，当数组中存在大量的重复数字时，就会破坏二分查找法的机制，将无法取得 O(lgn) 的时间复杂度，又将会回到简单粗暴的 O(n)，比如这两种情况：{2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2} 和 {2, 2, 2, 0, 2, 2, 2, 2, 2, 2, 2, 2}，可以发现，当第一个数字和最后一个数字，还有中间那个数字全部相等的时候，二分查找法就崩溃了，因为它无法判断到底该去左半边还是右半边。这种情况下，将右指针左移一位（或者将左指针右移一位），略过一个相同数字，这对结果不会产生影响，因为只是去掉了一个相同的，然后对剩余的部分继续用二分查找法，在最坏的情况下，比如数组所有元素都相同，时间复杂度会升到 O(n)，参见代码如下：

解法一：

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

跟之前那道 Find Minimum in Rotated Sorted Array 一样，还是可以用分治法 Divide and Conquer 来解，不过写法跟之前那道略有不同，只有在 nums[start] < nums[end] 的时候，才能返回 nums[start]，等于的时候不能返回，比如 [3, 1, 3] 这个数组，或者当 start 等于 end 成立的时候，也可以直接返回 nums[start]，后面的操作跟之前那道题相同，每次将区间 [start, end] 从中间 mid 位置分为两段，分别调用递归函数，并比较返回值，每次取返回值较小的那个即可，参见代码如下：

解法二：

class Solution {
public:
    int findMin(vector<int>& nums) {
        return helper(nums, 0, (int)nums.size() - 1);
    }
    int helper(vector<int>& nums, int start, int end) {
        if (start == end) return nums[start];
        if (nums[start] < nums[end]) return nums[start];
        int mid = (start + end) / 2;
        return min(helper(nums, start, mid), helper(nums, mid + 1, end));
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/154

类似题目：

Find Minimum in Rotated Sorted Array

参考资料：

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/discuss/48808/My-pretty-simple-code-to-solve-it

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/discuss/167981/Beats-100-Binary-Search-with-Explanations

到此这篇关于C++实现LeetCode(154.寻找旋转有序数组的最小值之二)的文章就介绍到这了,更多相关C++实现寻找旋转有序数组的最小值之二内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(146.近最少使用页面置换缓存器)

    [LeetCode] 146. LRU Cache 最近最少使用页面置换缓存器 Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exist

  • C++实现LeetCode(151.翻转字符串中的单词)

    [LeetCode] 151.Reverse Words in a String 翻转字符串中的单词 Given an input string, reverse the string word by word. For example, Given s = "the sky is blue", return "blue is sky the". Update (2015-02-12): For C programmers: Try to solve it in-p

  • C++实现LeetCode(150.计算逆波兰表达式)

    [LeetCode] 150.Evaluate Reverse Polish Notation 计算逆波兰表达式 Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. Note: Division between two integ

  • C++实现LeetCode(148.链表排序)

    [LeetCode] 148. Sort List 链表排序 Sort a linked list in O(n log n) time using constant space complexity. Example 1: Input: 4->2->1->3 Output: 1->2->3->4 Example 2: Input: -1->5->3->4->0 Output: -1->0->3->4->5 常见排序方法有

  • C++实现LeetCode(153.寻找旋转有序数组的最小值)

    [LeetCode] 153. Find Minimum in Rotated Sorted Array 寻找旋转有序数组的最小值 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]). Find the minimum element. You may

  • C++实现LeetCode(149.共线点个数)

    C++实现LeetCode(149.共线点个数)

    [LeetCode] 149. Max Points on a Line 共线点个数 Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. Example 1: Input: [[1,1],[2,2],[3,3]] Output: 3 Explanation: ^ | |        o |     o |  o   +------------->

  • C++实现LeetCode(147.链表插入排序)

    C++实现LeetCode(147.链表插入排序)

    [LeetCode] 147. Insertion Sort List 链表插入排序 Sort a linked list using insertion sort. A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list. With each iteration one element (red) is

  • C++实现LeetCode(152.求最大子数组乘积)

    [LeetCode] 152. Maximum Product Subarray 求最大子数组乘积 Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product. Example 1: Input: [2,3,-2,4] Output: 6 Explanation: [2,3] has

  • C++实现LeetCode(154.寻找旋转有序数组的最小值之二)

    [LeetCode] 154. Find Minimum in Rotated Sorted Array II 寻找旋转有序数组的最小值之二 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]). Find the minimum element. Th

  • C++实现LeetCode(81.在旋转有序数组中搜索之二)

    [LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索之二 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]). You are given a target value to search.

  • C++实现LeetCode(33.在旋转有序数组中搜索)

    [LeetCode] 33. Search in Rotated Sorted Array 在旋转有序数组中搜索 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If f

  • C++实现LeetCode(88.混合插入有序数组)

    [LeetCode] 88. Merge Sorted Array 混合插入有序数组 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1and nums2 are m and n respectively. You may assume that nums1 has

  • java 求解二维数组列最小值

    java 求解二维数组列最小值

    java 求解二维数组列最小值 比较二维数组列最小值,组成一个新数组返回. 实现核心算法,不需要使用IO 输入:{{5,6,1,16},{7,3,9}} 输出:{1,3} import java.util.Arrays; public class Col { public static int[] getColMin(int a[][]) { int[] res = new int[a.length]; for (int i = 0; i < a.length; i++) { int[] s =

  • php实现有序数组旋转后寻找最小值方法

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转. 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素. 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1. NOTE:给出的所有元素都大于0,若数组大小为0,请返回0. 1.利用二分法寻找数组中的最小元素 2.定义两个 指针left和right,指向数组的第一个元素和最后一个元素,定义一个中间指针mid 3.如果arr[left]小于arr[mid],那么把左边指针移动到mid处,mid从

  • Python寻找两个有序数组的中位数实例详解

    Python寻找两个有序数组的中位数实例详解

    Python寻找两个有序数组的中位数 审题: 1.找出意味着这是一个查找算法题 2.算法复杂度log级别,就是提示你是二分查找 3.二分查找实现一般为递归 (1)递归包括递归体  (2)终止条件 思路: 定理: 1.有序数组中有一半的元素小于等于数组的中位数,有一半的元素大于等于中位数(如果数组中元素个数是奇数,那么这里的一半并不是严格意义的1/2) 2.如果我们去掉其中一个数组比中位数小的k个数,再去掉另一个数组中比中位数大的k个数,得到的合并子数组的中位数和原来的中位数相同. eg:[1,2

  • C++实现LeetCode(34.在有序数组中查找元素的第一个和最后一个位置)

    [LeetCode] 34. Find First and Last Position of Element in Sorted Array 在有序数组中查找元素的第一个和最后一个位置 Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm's runtime complexity

  • C++实现LeetCode(两个有序数组的中位数)

    [LeetCode] 4. Median of Two Sorted Arrays 两个有序数组的中位数 There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and 

随机推荐