033 Search in Rotated Sorted Array[M]

03-04

1 題目描述

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.

難度：Medium

2 題目樣例

無

3 題意分析

給出一個「旋轉」過一次的數組，尋找給定元素的下標。

個人感覺這裡用rotated不太合適，可能應該叫swaped？總之就是將數組 $[a_1,a_2..a_{pivot-1},a_{pivot}..a_{n-1},a_n]$ 變成 $[a_{pivot}...a_{n-1},a_n,a_1,a_2...a_{pivot-1}]$

4 思路分析

1 翻轉回來+二分

很簡單的想法，遍歷一次把數組轉回來然後一次二分搞定。注意的細節是返回下標的時候要換算。

代碼如下

class Solution {public: int search(vector<int>& nums, int target) { int len = nums.size(); int pivo=0; int offset; deque<int> q; int i; for(i=1;i<len;i++){ q.push_back(nums[i-1]); if(nums[i]<nums[i-1]){ pivo = i; for(int j=len-1;j>=i;j--) q.push_front(nums[j]); break; } } if(len==i) q.push_back(nums[len-1]); auto it = lower_bound(q.begin(),q.end(),target); if(it==q.end() || *it != target) return -1; offset = it - q.begin(); if(offset>=len-pivo) return offset - (len-pivo); else return offset + pivo; }};

整體時間複雜度為 $O(n)$ ，空間複雜度為 $O(n)$ 。

2 二分搜索

之前的演算法還沒有把原數組有序這個條件用到極致，因此還有優化空間。

對於給定的數組 $[a_{pivot}...a_{n-1},a_n,a_1,a_2...a_{pivot-1}]$ ，我們知道有 $a_{pivot}<a_{pivot+1}...<a_n$ 並且 $a_1<a_2<...<a_{pivot}$ ，也就是說對於任意一個元素 $a_i$ 我們有

如果 $a_{pivot} le a_i$ ，那麼一定有 $a_i in [a_{pivot}...a_n]$ ，並且 $[a_{pivot}...a_i]$ 有序
如果 $a_ile a_{pivot-1}$ ，那麼一定有 $a_i in [a_1...a_{pivot-1}]$ ，並且 $[a_i...a_{pivot-1}]$ 有序

是不是跟二分有點像？沒錯，在一般的二分過程中我們利用的是目標元素和數組中間元素大小關係來確定下次搜索的區間，在這裡我們利用和 $a_{pivot},a_{pivot-1}$ 的大小關係來確定下次搜索的區間，本質上都是一致的。

假設要搜索的區間為 $[left,right]$ 有

如果 $a_{mid} == target$ ，直接返回
如果 $a_{left} le a_{mid}$ 那麼 $[left,mid]$ 有序，很容易（ $O(1)$ 的時間）判斷 $target$ 是否在 $[left,mid]$ 中，如果在的話下次搜索的區間為 $[left,mid-1]$ ，否則下次搜索的區間為 $[mid+1,right]$
如果 $a_{mid} le a_{right}$ 同理 $[mid,right]$ 有序，如果 $target$ 在 $[mid,right]$ 中，那麼下次搜索區間為 $[mid+1,right]$ ，否則為 $[left,mid-1]$

注意這個過程即使 $[left,right]$ 沒有翻轉本身已經有序也是成立的。

代碼如下

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

整體時間複雜度 $O(lgn)$ ，空間複雜度 $O(1)$ 。

5 後記

我非常喜歡這道題，簡直太優美了。