leetcode153-154 find minimum rotated sorted array

DrizzleX 发布于2019-08-16 10:42 / 2301人阅读

摘要：题目要求假设有一个升序排序的数组，在某个节点处断开并调换了顺序。寻找这个断开数组中的最小元素。但是如果我们将头尾的重复元素清楚，而只是在数组中间存在重复元素的话，如，这样并不会影响升序数组位置的判断。

题目要求

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.

假设有一个升序排序的数组，在某个节点处断开并调换了顺序。寻找这个断开数组中的最小元素。

当数组中不存在重复的元素

通过二分法来实现在logN的时间中找到最小的值。通过二分法往往会有以下几种情况

位于一个升序的数组中，也就是左侧值小于右侧值，这时候左侧值就是最小值。

左侧值小于中间值，那么中间值左侧一定是升序数组，所以最小值在右侧

中间值小于右侧值，那么中间值右侧一定是升序数组，所以最小值要么在左侧，要么就是中间值

代码如下：

    public int findMin(int[] nums) {
        int leftPointer = 0;
        int rightPointer = nums.length-1;
        while(leftPointer
数组中存在重复的元素
唯一会影响遍历的是数组的开头和结尾处的元素为重复元素，如[4,4,1,4,4]，在这种情况下就无法通过上面一种方法来识别出升序数组位于中间值的左侧或是右侧。但是如果我们将头尾的重复元素清楚，而只是在数组中间存在重复元素的话，如[4,1,1,1,3]，这样并不会影响升序数组位置的判断。
  public int findMin2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Integer.MIN_VALUE;
        }
        
        int start = 0, end = nums.length - 1;
        
        while (nums[end] == nums[start] && end > start) {
            end--;
        }
        
        while (start < end) {
            if (nums[start] < nums[end]) {
                return nums[start];
            }
            
            int mid = start + (end - start) / 2;
            if (nums[mid] >= nums[start]) {
                start = mid + 1;
            }
            else {
                end = mid;
            }
        }
        
        return nums[start];
    }  

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

云服务器 GPU云服务器 sorted-array array_find Minimum Leetcod

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70285.html

[LintCode/LeetCode] Find Minimum in Rotated Sorted

摘要：排序数组中找最小值或最大值的题目，很明显可以使用二分法。因此，只判断终点和中点元素的大小关系即可。这里有一种情况是上述后三个，中点值和末位相等。此时，两边同时递归，并返回两边递归值的较小值。当首位和末位重合，说明已夹逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...

cgh1999520 2019-08-14 15:22 评论0 收藏0
[Leetcode] Find Minimum in Rotated Sorted Array 找旋

摘要：二分迭代法复杂度时间空间递归栈空间思路找旋转数组的起点，实际上类似找一个山谷，只要两边都比中间高就对了，这和这题很像。 Find Minimum in Rotated Sorted Array I Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 ...

notebin 2019-08-14 12:24 评论0 收藏0
Find Minimum in Rotated Sorted Array

摘要：题目思路个人觉得这是一道值得回味的二分法题目。与给出的二分法搜索比，这道题目的是未知的，并且是。我个人是从观察给出的例子入手的。我本人走的弯路是，过于专注于，从而逻辑变得复杂。其实，，和步就可以帮助我们顺利找到最小值。题目 http://www.lintcode.com/en/pr... Suppose a sorted array is rotated at some pivot ...

DataPipeline 2019-07-30 14:38 评论0 收藏0
LeetCode 154 在有序旋转数组中找最小-2

摘要：难度就是说一个从小到大排序好的数组循环移位不知多少次，求最小值。比如全部是的数列，和除了某位置有个，其余全部是的数列，都是合法的。在这里，测试用例也进行了增加，尽量覆盖各种奇葩情况。 Follow up for Find Minimum in Rotated Sorted Array:What if duplicates are allowed?Would this affect th...

evin2016 2019-08-14 17:02 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0