[LeetCode] 81. Search in Rotated Sorted Array II

轉自LeetCode

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

<Solution>

這題是 Search in Rotated Sorted Array 的衍生題

差別在於，這次 array 裡面可以有重複的值

思路還是一樣，但在檢查是否有旋轉的時候

變成

bool isRotate = (nums.front() >= nums.back()) ? true : false;
也就是將下列兩種狀況視為同一種

2 2 1 2 2 和 3 4 5 6 1 2

剩下的部分，就和之前一樣

只在 search 的地方，有做一些 skip duplicates 的動作來加速

code 如下


也可以只使用 binary search

但要特別處理重複值的時候，舉例 [3,1,1] 和 [1,1,3,1]

這兩個在做 binary search 的時候，3 有可能在左半部，也有可能在右半部

所以當 nums[mid] = nums[right] 的時候，把 right 往前移來繼續尋找的動作

當 nums[mid] < nums[right]，就代表右半部是有排序的

當 nums[mid] > nums[right]，就代表左半部是有排序的

kotlin