leetcode 33 Search in Rotated Sorted Array

diabloneo 發布于2019-08-16 11:04 / 1327人閱讀

摘要：如正常的升序排列應該是，，，，，，旋轉過后可能就是，，，，，，。想法因為這是一個經過旋轉的升序數組，我們可以將其看作兩個升序的序列，，，和，，。如果在前一個序列，則從前面進行查找。如果在后面一個序列，則從最后一個元素開始查找。

題目詳情

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

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

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