【LeetCode】154. Find Minimum in Rotated Sorted Array II 寻找旋转排序数组中的最小值 II（Hard）（JAVA）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【LeetCode】154. Find Minimum in Rotated Sorted Array II 寻找旋转排序数组中的最小值 II（Hard）（JAVA），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1920字，纯文字阅读大概需要3分钟。

内容图文

【LeetCode】154. Find Minimum in Rotated Sorted Array II 寻找旋转排序数组中的最小值 II（Hard）（JAVA）

题目地址: https://leetcode.com/problems/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?

题目大意

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

说明：

• 这道题是 寻找旋转排序数组中的最小值 的延伸题目。
• 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

解题方法

1. 和上一题类似，只是上一题所有元素都是唯一的，这一题元素可能是重复的
2. 遇到 nums[start] < nums[end] 我们可以直接得出结果
3. 但是遇到 nums[start] == nums[mid] 时，因为可能是 start == mid（这时候 end = start + 1，已经知道 nums[start] >= nums[end]），直接 start++ 即可；如果 start != mid，反正后面还有相同元素，也可以 start++
4. nums[start] < nums[mid]，结果在 [mid + 1, end] 之间
5. nums[start] > nums[mid]，结果在 [start + 1, mid] 之间
6. note: 如果重复元素过多，判断 nums[start] == nums[mid]，我们都是 start++，最后就会变成 O(n) 的时间复杂度

class Solution {
    public int findMin(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            if (start == end) return nums[start];
            if (nums[start] < nums[end]) return nums[start];
            int mid = start + (end - start) / 2;
            if (nums[start] == nums[mid]) {
                start++;
            } else if (nums[start] < nums[mid]) {
                start = mid + 1;
            } else {
                end = mid;
                start++;
            }
        }
        return 0;
    }
}

执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:38 MB,击败了97.67% 的Java用户

内容总结

以上是互联网集市为您收集整理的【LeetCode】154. Find Minimum in Rotated Sorted Array II 寻找旋转排序数组中的最小值 II（Hard）（JAVA）全部内容，希望文章能够帮你解决【LeetCode】154. Find Minimum in Rotated Sorted Array II 寻找旋转排序数组中的最小值 II（Hard）（JAVA）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端