leetcode33 search in rotated sorted array

MkkHou 發(fā)布于2019-08-14 18:11 / 1830人閱讀

摘要：這里相比于思路一，更適用于目標節(jié)點在中間的情況，而思路一在目標節(jié)點分布在數(shù)組兩側會效率更高。

題目要求

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.

You may assume no duplicate exists in the array.

翻譯過來就是說：一個由小到大有序排列的數(shù)組被分為兩個子數(shù)組，這兩個子數(shù)組調(diào)換前后順序生成一個新數(shù)組。在新數(shù)組中找到目標值并返回下標

思路一：雙指針

左右同時比較，直至找到目標值或是左右指針相遇

    public int search(int[] nums, int target){ 
        int left = 0;
        int right = nums.length - 1;
        while(left<=right){
            if(nums[left]==target){
                return left;
            }
            if(nums[right] == target){
                return right;
            }
            left++;
            right--;
        }
        return -1;
    }

思路二：二分法查找

思路一并沒有充分利用條件，及這個數(shù)組是由兩個有序的子數(shù)組合成的。這里我們可以使用二分法的一個變形的算法。先找到中間節(jié)點，這個中間節(jié)點如果不是在左順序子數(shù)組，就一定在右順序子數(shù)組，反之亦成立。這樣我們就可以變相的使用二分法將區(qū)間范圍逐漸縮小，直至找到目標值。
這里相比于思路一，更適用于目標節(jié)點在中間的情況，而思路一在目標節(jié)點分布在數(shù)組兩側會效率更高。

    public int search(int[] nums, int target){ 
        int left = 0;
        int right = nums.length - 1;
        while(left<=right){
            int mid = (left + right)/2;
            int midNum = nums[mid];
            if(midNum==target){
                return mid;
            }
            if(nums[left]<=midNum){
                if(nums[left]<=target && midNum>target){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }
            if (midNum <= nums[right]){
                if (target > midNum && target <= nums[right])
                    left = mid + 1;
                 else
                    right = mid - 1;
            }
        }
        return -1;
    }

想要了解更多開發(fā)技術，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關注我的微信公眾號！將會不定期的發(fā)放福利哦~

云服務器 GPU云服務器 sorted-array array_search函數(shù) in_array() in_array

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

轉載請注明本文地址：http://systransis.cn/yun/67054.html

leetcode 33 Search in Rotated Sorted Array

摘要：如正常的升序排列應該是，，，，，，旋轉過后可能就是，，，，，，。想法因為這是一個經(jīng)過旋轉的升序數(shù)組，我們可以將其看作兩個升序的序列，，，和，，。如果在前一個序列，則從前面進行查找。如果在后面一個序列，則從最后一個元素開始查找。題目詳情 Suppose an array sorted in ascending order is rotated at some pivot unknown...

diabloneo 2019-08-16 11:04 評論0 收藏0
leetcode-33-Search in Rotated Sorted Array

摘要：由于不是一直升序，所以需要多些條件進行范圍的限定。注意邊界值的確定，有邊界值相等，列表只有一個值，這些情況。注意的使用應用排序，快速確定某個值的位置題目闡釋：給定一組升序數(shù)組，取某個點之后將數(shù)組截斷交換前后兩個數(shù)組順序，給定一個值，求這個值的index 重點：二分法，確定target在哪個列表中，之后不斷二分法進行位置確認。由于不是一直升序，所以需要多些條件進行范圍的限定...

SKYZACK 2019-07-30 17:19 評論0 收藏0
[Leetcode] Search in Rotated Sorted Array 搜索旋轉有序數(shù)組

摘要：如果左邊的點比右邊的大，說明這兩個點之間有一個旋轉點，導致了不再有序。因為只有一個旋轉點，所以一分為二后，肯定有一半是有序的。 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

摘要：找中點若起點小于中點，說明左半段沒有旋轉，否則說明右半段沒有旋轉。在左右半段分別進行二分法的操作。只判斷有無，就容易了。還是用二分法優(yōu)化 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

摘要：題目要求相比于，中添加了數(shù)組中可能存在重復值的條件。這是我們可以將情況分為以下幾種。因為如果而且，則左側或右側的子數(shù)組至少有一個為順序的數(shù)組，這違背題目要求。所喲一定是同理，如果，那么。題目要求 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. ...

Cheriselalala 2019-08-15 10:35 評論0 收藏0