示例 1:
輸入: nums = [4,5,6,7,0,1,2], target = 0
輸出: 4
示例 2:
輸入: nums = [4,5,6,7,0,1,2], target = 3
輸出: -1

問題分析

首先個人認(rèn)為題目中的“旋轉(zhuǎn)”可能并不直觀，不利于理解，在這里旋轉(zhuǎn)也可以認(rèn)為是數(shù)組向右循環(huán)移動，何為循環(huán)移動，看下面

1, 2, 3, 4, 5 循環(huán)向右移動一位 為 5, 1, 2, 3, 4
1, 2, 3, 4, 5 循環(huán)向右移動兩位 為 4, 5, 1, 2, 3

題目要求時間復(fù)雜度O(logN)，而且數(shù)組是排序的，肯定是二分法了。但是這個數(shù)組卻并不是一個完全遞增的數(shù)組，他的特點是

數(shù)組中存在一個位置index，A = [0, index)遞增序列，B = [index, size)是一個遞增序列

遞增序列A中的任意一個元素均大于遞增序列B的任意一個元素，用數(shù)學(xué)表示的話就是

對于特點2可能不是很明顯，理由如下：

題中的旋轉(zhuǎn)可以認(rèn)為進行了X次的向右循環(huán)移動

每次向右循環(huán)移動都會將最后一位數(shù)移動到最左邊

根據(jù) 特點1 和 理由2 可知每次被移動到左邊的數(shù)字為序列B中最大的元素，移動過后這個元素進入了序列A的最左邊，也就是說這個元素成為了序列A中最小的元素

根據(jù)上述三條理由確定一個在每次循環(huán)右移之后都成立的條件：

每次循環(huán)右移到數(shù)組最左邊的元素都是大于遞增序列B的任何一個數(shù)的，且這個元素是遞增序列A中最小的一個元素

或者可以表述為

每次循環(huán)右移到遞增序列A最左邊的元素都是大于遞增序列B中的任何一個元素，且這個元素是遞增序列A中最小的一個元素

所以進行了X次向右循環(huán)移動的數(shù)組依舊滿足 理由4 的結(jié)論，所以 特點2 成立

解法一：數(shù)組中的最小值，對左右兩邊各進行一次二分查找

很明顯，數(shù)組的最小值就是遞增序列B的第一項。最小值的左邊（不包括旋最小值）是一個遞增序列，最小值的右邊（包括最小值）是一個遞增數(shù)列。

不是很清楚的讀者可以在下圖，紅線圈住的值就是最小值，也可以很輕易地看出上述規(guī)律。

由于題目要求時間復(fù)雜度O(lgn),所以我們必須在O(lgn)的時間內(nèi)找到最小值，具體如何找呢？肯定還是二分搜索的思想，不過要分情況考慮了。

當(dāng) nums[mid] > nums[0] 時

應(yīng)該是下圖所示的情況，很明顯，最小是在二分點的右邊，所以應(yīng)該是移動左指針，即

left = mid + 1;

當(dāng) nums[mid] < nums[0] 時

應(yīng)該是下圖所示的情況，很明顯，最小值在二分點的左邊，應(yīng)該移動右指針，即

right = mid - 1;

不過我們少考慮的一種情況，也就是如果整個數(shù)組是一個完全遞增的數(shù)組，也就是并沒有經(jīng)過任何變化，那么上述方法的到的最終結(jié)果就是會出出錯，所以在二分結(jié)果后需要再做一個判斷，判斷數(shù)組的第一位和二分查找得到的結(jié)果那個小，即

if nums[0] < nums[mid]minIndex = 0; elseminIndex = mid;

所以尋找旋轉(zhuǎn)點的最終偽代碼為：

findMin(nums)// nums is a arrayleft = 0;right = nums.length - 1;while left <= rightmid = (left + right) / 2;// 判斷是否是最小值，也就是左右都比它大if nums[mid] is smaller than left and right valuesbreak;else if nums[mid] > nums[0]left = mid + 1;elseright = mid - 1;if nums[0] < nums[mid]minIndex = 0;elseminIndex = mid;return midIndex;

現(xiàn)在我們找到了最小值了，就可以以最小值為分界點分別對左右兩個遞增序列進行二分查找了，所以整個程序的偽碼如下：

search(nums,target)/*nums is a arraytarget is a number*/minIndex = findMin(nums);left = 0;right = minIndex - 1;while left <= rightmid = (left + right) / 2;if nums[mid] == targetreturn mid;else if target < nums[mid]right = mid - 1;elseleft = mid + 1;left = minIndex;right = nums.length - 1;while left <= rightmid = (left + right) / 2;if nums[mid] == targetreturn mid;else if target < nums[mid]right = mid - 1;elseleft = mid + 1;

時空復(fù)雜度分析

找出旋轉(zhuǎn)點O(lgn),兩次二分查找均為O(lgn)，算法總時間復(fù)雜度為O(lgn)

算法使用了常數(shù)空間，空間復(fù)雜度為O(1)

解法二：直接通過二分法找出目標(biāo)值

這里會稍微復(fù)雜一些，依舊先分情況討論

當(dāng) nums[mid] > nums[0] 且 nums[mid] < target

從圖上來看，二分點在目標(biāo)值的左邊，所以應(yīng)該移動左指針，即

left = mid + 1;

當(dāng) nums[mid] > nums[0] 且 nums[mid] > target 且 nums[0] < target

從圖上看，二分點在目標(biāo)值右邊，所以應(yīng)該移動右指針，即

right = mid - 1;

當(dāng) nums[mid] > nums[0] 且 nums[mid] > target 且 nums[0] > target

從圖上來看，二分點在目標(biāo)值的左邊，應(yīng)該移動左指針，即

left = mid + 1;

當(dāng) nums[mid] < nums[0] 且 nums[mid] > target

從圖上來看，二分點在目標(biāo)值的右邊，應(yīng)該移動右指針，即

right = mid - 1;

當(dāng) nums[mid] < nums[0] 且 nums[mid] < target 且 nums[0] > target

從圖上來看，二分點在目標(biāo)值的左邊，應(yīng)該移動左指針，即

left = mid + 1;

當(dāng) nums[mid] < nums[0] 且 nums[mid] < target 且 nums[0] < target

從圖上來看，二分點在目標(biāo)值的右邊，應(yīng)該移動右指針，即

right = mid - 1;

當(dāng) nums[mid] = nums[0]

從圖上來看，目標(biāo)值肯定在二分點的右邊（暫不考慮目標(biāo)值在最左端的情況）,應(yīng)該移動左指針，即

left = mid + 1;

當(dāng)目標(biāo)值位于數(shù)組兩端

在程序最開始時做判斷即可

所以整個程序的偽代碼應(yīng)該為：

search(nums, target)/*nums is a arraytarget is a number*/left = 0;right = nums.length - 1;if nums[0] == targetreturn 0;if nums[nums.length - 1] == targetreturn nums.length - 1;while left <= rightmid = (left + right) / 2;if nums[mid] == targetreturn mid;elseif nums[mid] > nums[0]if target > nums[mid]left = mid + 1;elseif target > nums[0]right = mid - 1;elseleft = mid + 1;else if nums[mid] < nums[0]if target < nums[mid]right = mid - 1;elseif target < nums[nums.size() - 1]left = mid + 1;elseright = mid - 1;elseleft = mid + 1;return -1;

時空復(fù)雜度分析

時間復(fù)雜度為O(lgn),空間復(fù)雜度O(1)

轉(zhuǎn)載于:https://www.cnblogs.com/FDProcess/p/10614145.html

總結(jié)

以上是生活随笔為你收集整理的[LeetCode] 搜索旋转排序数组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。