Last Updated on 2022-03-28 by Clay
題目
There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).
Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].
Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.
You must decrease the overall operation steps as much as possible.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0 Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3 Output: false
Constraints:
1 <= nums.length <= 5000-104 <= nums[i] <= 104numsis guaranteed to be rotated at some pivot.-104 <= target <= 104
Follow up: This problem is similar to Search in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?
題目給定一純數值陣列，本來陣列應是由小到大排序，但會在某個特定樞點（pivot）將後續的所有數值列表嫁接到前排。比方說原本的陣列 [1, 2, 3, 4] 可能會在 index=2 時為樞點，讓陣列變成 [3, 4, 1, 2]。
另外我們還會得到一個目標值 target。如果目標值存在於陣列，回傳 true，反之回傳 false。
解題思路
這題可以很單純地使用遍歷暴力法（也可以利用排序特性做點優化）、也可以用二元搜索（binary search）來減低複雜度。
不過或許是我有沒考慮到的地方，我在使用優化過的遍歷搜尋上比二元搜索來得效率更好。明明時間複雜度應該是二元搜索佔優才是。
Brute Force 解法
首先，我們可以理所當然地使用遍歷來搜索目標值 target。不過若當前搜索的值大於 target、且前一個值小於 target，則代表 target 一定不存在於這個陣列，可以直接回傳 false。
要注意的是反過來則不一定：如果當前值小於 target 且前一個值大於 target，有可能只是碰上 pivot 轉換的點。
Brute Force 複雜度
因為理論上我們需要遍歷列表，故時間複雜度為 O(n)；不需要儲存儲了讀取索引以外的值，故空間複雜度為 O(1)。
| Time complexity | O(n) |
| Space complexity | O(1) |
Brute Force 解法 C++ 範例程式碼
class Solution {
public:
bool search(vector<int>& nums, int target) {
for (int i=0; i<nums.size(); ++i) {
if (nums[i] == target) return true;
if (i >= 1 && nums[i-1] < target && nums[i] > target) {
return false;
}
}
return false;
}
};Brute Force 解法 Python 範例程式碼
for i in range(len(nums)):
if nums[i] == target:
return True
if i >= 1 and nums[i-1] < target and nums[i] > target:
break
return False二元搜索法
跟通常性的二元搜索法相比，我們需要注意（以下用 left 當作左側邊界值、right 當作右側邊界值、mid 當作中間值）：
- 如果 left == mid、且 right == mid，left 需要加一、right 需要減一（這是因為列表中可能存在相同的值，而我們在找不到目標值時不需要考慮相同值）
- 如果 left <= mid 則代表此段仍在遞增中，如果 left < target < mid，則可以將 right 賦值成 mid-1，以此縮小搜尋 target 的範圍（反之則 left = mid + 1）
- 如果 left > mid 則代表此處是遞減段落，如果 mid < target < right，這次則將 left = mid + 1 來縮小搜尋範圍（反之則 right = mid - 1）
如果到最後 left > right 我們都還沒在搜尋邊界中找到目標值，則代表目標值不存在於陣列中。
二元搜索複雜度
| Time complexity | O(log n) |
| Space complexity | O(1) |
二元搜索解法 C++ 範例程式碼
class Solution {
public:
bool search(vector<int>& nums, int target) {
// Init
int left = 0;
int right = nums.size() - 1;
// Finding
while (left <= right) {
int mid = left + (right-left) / 2;
if (nums[mid] == target) return true;
if ((nums[left] == nums[mid]) && (nums[right] == nums[mid])) {
++left;
--right;
}
else if (nums[left] <= nums[mid]) {
if ((nums[left] <= target) && (nums[mid] > target)) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
else {
if ((nums[right] >= target) && (nums[mid] < target)) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
}
return false;
}
};二元搜索解法 Python 範例程式碼
class Solution:
def search(self, nums: List[int], target: int) -> bool:
# Init
left = 0
right = len(nums) - 1
# Finding
while left <= right:
mid = left + (right-left) // 2
# If hit the target
if nums[mid] == target:
return True
if nums[left] == nums[mid] and nums[right] == nums[mid]:
left += 1
right -= 1
elif nums[left] <= nums[mid]:
if nums[left] <= target and nums[mid] > target:
right = mid - 1
else:
left = mid + 1
else:
if nums[right] >= target and nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return False