國內(nèi)優(yōu)秀網(wǎng)頁設(shè)計網(wǎng)站西安百度代運營
題目描述
整數(shù)數(shù)組 nums
按升序排列,數(shù)組中的值 互不相同 。
在傳遞給函數(shù)之前,nums
在預(yù)先未知的某個下標(biāo) k
(0 <= k < nums.length
)上進行了 旋轉(zhuǎn),使數(shù)組變?yōu)?[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(下標(biāo) 從 0 開始 計數(shù))。例如, [0,1,2,4,5,6,7]
在下標(biāo) 3
處經(jīng)旋轉(zhuǎn)后可能變?yōu)?[4,5,6,7,0,1,2]
。
給你 旋轉(zhuǎn)后 的數(shù)組 nums
和一個整數(shù) target
,如果 nums
中存在這個目標(biāo)值 target
,則返回它的下標(biāo),否則返回 -1
。
你必須設(shè)計一個時間復(fù)雜度為 O(log n)
的算法解決此問題。
示例 1:
輸入:nums = [4,5,6,7,0,1,2], target = 0
輸出:4
示例 2:
輸入:nums = [4,5,6,7,0,1,2], target = 3
輸出:-1
示例 3:
輸入:nums = [1], target = 0
輸出:-1
提示:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums
中的每個值都 獨一無二- 題目數(shù)據(jù)保證
nums
在預(yù)先未知的某個下標(biāo)上進行了旋轉(zhuǎn) -104 <= target <= 104
解答
class Solution {
public:// 采用二分法int search(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1;while(l <= r){int mid = (l + r) >> 1;if(target == nums[mid]) return mid;// 旋轉(zhuǎn)后產(chǎn)生左右兩個升序序列// l ~ mid 都在左邊的升序序列中if(nums[l] <= nums[mid]){// 范圍確定在[l, mid)if(target >= nums[l] && target < nums[mid]) r = mid - 1;// target < nums[l] || target >= midelse l = mid + 1;}else // l~mid 一部分在左邊,一部分在右邊{if(target > nums[mid] && target <= nums[r]) l = mid + 1;else r = mid - 1;}}return -1;}int search1(vector<int>& nums, int target) {vector<int>::iterator iter = find(nums.begin(), nums.end(), target);return iter != nums.end() ? iter - nums.begin() : -1;}
};