[LintCode/LeetCode] Search in Rotated Sorted Arra

U2FsdGVkX1x 發布于2019-08-14 15:41 / 3615人閱讀

摘要：找中點若起點小于中點，說明左半段沒有旋轉，否則說明右半段沒有旋轉。在左右半段分別進行二分法的操作。只判斷有無，就容易了。還是用二分法優化

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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