Search in Rotated Sorted Array II (M)
題目
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
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
Follow up:
- This is a follow up problem to Search in Rotated Sorted Array, where
numsmay contain duplicates. - Would this affect the run-time complexity? How and why?
題意
將一非遞減數列的隨機后半部分與前半部分換位，得到新陣列，在新陣列中查找目標值，
思路
與 33. Search in Rotated Sorted Array 相比，允許陣列中存在重復的值，這帶來的問題是，很難根據一個元素與最左側元素的大小關系來判斷它是落在左區間還是右區間，如陣列 [2, 2, 2, 3, 4, 5, 2, 2]，
因此在 33. Search in Rotated Sorted Array 解法的基礎上做出改動：只有當nums[mid]與nums[left]存在嚴格的大于小于關系時，才能確定mid是落在左區間還是右區間，而當nums[mid]等于nums[left]時，因為無法有效判斷區間歸屬，只能令left右移(或者right左移)，在最壞情況下(全元素一樣)，時間復雜度退化至\(O(N)\)，
代碼實作
Java
class Solution {
public boolean search(int[] nums, int target) {
if (nums.length == 0) {
return false;
}
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return true;
}
// 只有嚴格的大于小于關系才能明確判斷落在左區間還是右區間
if (nums[mid] > nums[left]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else if (nums[mid] < nums[left]) {
if (target <= nums[right] && target > nums[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else {
left++;
}
}
return false;
}
}
JavaScript
/**
* @param {number[]} nums
* @param {number} target
* @return {boolean}
*/
var search = function (nums, target) {
let left = 0, right = nums.length - 1
while (left <= right) {
let mid = Math.trunc((right - left) / 2) + left
if (nums[mid] == target) {
return true
}
if (nums[mid] > nums[left] && target >= nums[left] && target < nums[mid]) {
right = mid - 1
} else if (nums[mid] > nums[left]) {
left = mid + 1
} else if (nums[mid] < nums[left] && target <= nums[right] && target > nums[mid]) {
left = mid + 1
} else if (nums[mid] < nums[left]) {
right = mid - 1
} else {
left++
}
}
return false
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/225604.html
標籤：其他