[LintCode/LeetCode] Search in Rotated Sorted Arra

U2FsdGVkX1x 发布于2019-08-14 15:41 / 3470人阅读

摘要：找中点若起点小于中点，说明左半段没有旋转，否则说明右半段没有旋转。在左右半段分别进行二分法的操作。只判断有无，就容易了。还是用二分法优化

Search in Rotated Sorted Array Problem

Suppose a sorted array 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.

You may assume no duplicate exists in the array.

Example

For [4, 5, 1, 2, 3] and target=1, return 2.

For [4, 5, 1, 2, 3] and target=0, return -1.

Challenge

O(logN) time

Note

找中点：若起点小于中点，说明左半段没有旋转，否则说明右半段没有旋转。
在左右半段分别进行二分法的操作。

Solution

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

Search in Rotated Sorted Array II Problem

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

Note

只判断有无，就容易了。

Solution

还是用二分法优化

public class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return false;
        int start = 0, end = nums.length-1;
        while (start <= end) {
            int mid = start+(end-start)/2;
            if (nums[mid] == target || nums[start] == target || nums[end] == target) return true;
            if (nums[start] < nums[mid]) {
                if (nums[start] <= target && target < nums[mid]) end = mid-1;
                else start = mid+1;
            }
            else if (nums[start] > nums[mid]) {
                if (nums[mid] < target && target <= nums[end]) start = mid+1;
                else end = mid-1;
            }
            else {
                if (nums[start] != target) start++;
                if (nums[end] != target) end--;
            }
        }
        return false;
    }
}

Updated 2018-08

class Solution {
    public boolean search(int[] nums, int target) {
        int start = 0, mid = 0, end = nums.length-1;
        while (start <= end) {
            mid = start+(end-start)/2;
            if (nums[mid] == target || nums[start] == target || nums[end] == target) return true;
            if (nums[start] < nums[mid]) {
                if (nums[start] < target && target < nums[mid]) end = mid-1;
                else start = mid+1;
            } else if (nums[start] > nums[mid]) {
                if (nums[mid] < target && target < nums[end]) start = mid+1;
                else end = mid-1;
            } else {
                start++;
                end--;
            }
        }
        return false;
    }
}

云服务器 GPU云服务器 Rotated Sorted sorted-array sorted_set

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

转载请注明本文地址：https://www.ucloud.cn/yun/65939.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] 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
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

摘要：如正常的升序排列应该是，，，，，，旋转过后可能就是，，，，，，。想法因为这是一个经过旋转的升序数组，我们可以将其看作两个升序的序列，，，和，，。如果在前一个序列，则从前面进行查找。如果在后面一个序列，则从最后一个元素开始查找。题目详情 Suppose an array sorted in ascending order is rotated at some pivot unknown...

diabloneo 2019-08-16 11:04 评论0 收藏0
[LintCode/LeetCode] Search Insert Position

Problem Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume NO duplicates in the a...

cjie 2019-08-14 15:40 评论0 收藏0