leetcode 81.?Search in Rotated Sorted Array II
這是一道m(xù)edium題甩牺，在做這道題之前蘑志，如果弄明白了leetcode 33.?Search in Rotated Sorted Array，那么做這道題目會(huì)簡單一些贬派。
33.?Search in Rotated Sorted Array 也是medium題急但。題目是說一個(gè)array是增序排列，但是呢以一個(gè)pivot做了rotate搞乏，pivot在哪個(gè)位置不定波桩，求給定的target是否在這個(gè)rotated array中存在。e.g,??Input:nums = [4,5,6,7,0,1,2], target = 0?Output:4(index)
my solution:
class Solution {
? ? public int search(int[] nums, int target) {
? ? ? ? int start =0, end = nums.length - 1;
? ? ? ? while(start<=end) {
? ? ? ? ? ? int mid = start + (end - start) / 2;
? ? ? ? ? ? if(nums[mid] == target) {
? ? ? ? ? ? ? ? return mid;
? ? ? ? ? ? } else if(nums[mid] < nums[start]) {
// we can only ensure the right part is sorted
? ? ? ? ? ? ? ? if(target > nums[mid] && target <= nums[end]) {
? ? ? ? ? ? ? ? ? ? start = mid + 1;
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? end = mid - 1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? } else {
// we can only ensure the left part is sorted
? ? ? ? ? ? ? ? if(target<nums[mid] && target >= nums[start]) {
? ? ? ? ? ? ? ? ? ? end = mid -1;
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? start = mid + 1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return -1;
? ? }
}
做完33查描，我們?cè)倏?1突委， 81是說這個(gè)rotated array里面的數(shù)字可以重復(fù)。
如果可以重復(fù)冬三，跟33的區(qū)別就是匀油，當(dāng)mid的值和start或者end相等的時(shí)候，你不知道應(yīng)該接下來取哪一半的值勾笆，因?yàn)榭赡躮id在pivot左邊敌蚜，也可能在右邊。為了避免這種情況窝爪，我們把start和end的兩邊重復(fù)的值去掉弛车，這樣可以保證mid的值至少不會(huì)與start或者end相同。這樣就能知道接下來取哪一邊的值蒲每。
class Solution {
? ? public boolean search(int[] nums, int target) {
? ? ? ? int start =0, end = nums.length - 1;
? ? ? ? while(start<=end) {
? ? ? ? ? ? while (start < end && nums[start] == nums[start + 1])
? ? ? ? ? ? ? ? ++start;
? ? ? ? ? ? while (start < end && nums[end] == nums[end - 1])
? ? ? ? ? ? ? ? --end;
? ? ? ? ? ? int mid = start + (end - start) / 2;
? ? ? ? ? ? if(nums[mid] == target) {
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? } else if(nums[mid] < nums[start]) {
? ? ? ? ? ? ? ? if(target > nums[mid] && target <= nums[end]) {
? ? ? ? ? ? ? ? ? ? start = mid + 1;
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? end = mid - 1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? if(target<nums[mid] && target >= nums[start]) {
? ? ? ? ? ? ? ? ? ? end = mid -1;
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? start = mid + 1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return false;
? ? }
}
這個(gè)time complexity: O(N)?worst case, O(logN)?best case, where?N is the length of the input array.
Worst case: This happens when all the elements are the same and we search for some different element. At each step, we will only be able to reduce the search space by 1 since?arr[mid]?equals?arr[start]?and it's not possible to decide the relative position of?target?from?arr[mid]. Example: [1, 1, 1, 1, 1, 1, 1], target = 2.
Best case: This happens when all the elements are distinct. At each step, we will be able to divide our search space into half just like a normal binary search.
space complexityO(1)
這道題還有一個(gè)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?
從剛剛的分析就可以看出纷跛，當(dāng)有重復(fù)值時(shí)，會(huì)讓我么不能用binary search邀杏，所以這時(shí)候就多了一個(gè)最壞情況和一個(gè)最好情況贫奠。最好情況就是跟33一樣。
