leetcode 33 Search in Rotated Sorted Array

diabloneo 发布于2019-08-16 11:04 / 1326人阅读

摘要：如正常的升序排列应该是，，，，，，旋转过后可能就是，，，，，，。想法因为这是一个经过旋转的升序数组，我们可以将其看作两个升序的序列，，，和，，。如果在前一个序列，则从前面进行查找。如果在后面一个序列，则从最后一个元素开始查找。

题目详情

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 found in the array return its index, otherwise return -1.题目的输入是一个被旋转过的升序排列数组。（如正常的升序排列应该是‘0，1，2，4，5，6，7’；旋转过后可能就是‘4，5，6，7，0，1，2’）。
我们的目标就是在这样一个旋转过的数组中，找出输入的目标数字，如果数字不存在，则返回－1，否则返回数字在数组中的位置。

想法

因为这是一个经过旋转的升序数组，我们可以将其看作两个升序的序列（4，5，6，7和0，1，2）。

接着我们就要判断我们要找的数字在哪个序列中。这个时候可以将target元素和数组的最后一个元素比较。如果target > nums[n-1] 就说明target元素应当在前一个序列中，反之则在后一个序列中。

如果在前一个序列，则从前面进行查找。如果在后面一个序列，则从最后一个元素开始查找。

解法

    public int search(int[] nums, int target) {
        if(nums.length == 0 || nums == null) return -1; 
        int length = nums.length;
        if(nums[length-1] == target)return length-1;
        else if(nums[length-1] > target){
            for(int i=length-1;i>=0;i--){
                if(nums[i] == target) return i;
                if(nums[i]  target) return -1;
            }
        }
        return -1;
    }

云服务器 GPU云服务器 sorted-array array_search函数 in_array() in_array

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

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

leetcode33 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 ...

MkkHou 2019-08-14 18:11 评论0 收藏0
leetcode-33-Search in Rotated Sorted Array

摘要：由于不是一直升序，所以需要多些条件进行范围的限定。注意边界值的确定，有边界值相等，列表只有一个值，这些情况。注意的使用应用排序，快速确定某个值的位置题目阐释：给定一组升序数组，取某个点之后将数组截断交换前后两个数组顺序，给定一个值，求这个值的index 重点：二分法，确定target在哪个列表中，之后不断二分法进行位置确认。由于不是一直升序，所以需要多些条件进行范围的限定...

SKYZACK 2019-07-30 17:19 评论0 收藏0
[Leetcode] Search in Rotated Sorted Array 搜索旋转有序数组

摘要：如果左边的点比右边的大，说明这两个点之间有一个旋转点，导致了不再有序。因为只有一个旋转点，所以一分为二后，肯定有一半是有序的。 Search 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 7 mi...

thursday 2019-08-14 12:38 评论0 收藏0
[LintCode/LeetCode] Search in Rotated Sorted Arra

摘要：找中点若起点小于中点，说明左半段没有旋转，否则说明右半段没有旋转。在左右半段分别进行二分法的操作。只判断有无，就容易了。还是用二分法优化 Search in Rotated Sorted Array Problem Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 ...

U2FsdGVkX1x 2019-08-14 15:41 评论0 收藏0
leetcode 81 Search in Rotated Sorted Array II

摘要：题目要求相比于，中添加了数组中可能存在重复值的条件。这是我们可以将情况分为以下几种。因为如果而且，则左侧或右侧的子数组至少有一个为顺序的数组，这违背题目要求。所哟一定是同理，如果，那么。题目要求 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. ...

Cheriselalala 2019-08-15 10:35 评论0 收藏0