[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 如下

	class Solution {
	public:
	bool search(vector<int>& nums, int target) {
	if(nums.empty()) {
	return false;
	}
	bool isRotated = (nums.front() >= nums.back()) ? true : false;
	//> abolutely not in nums
	if(isRotated && (target < nums.front() && target > nums.back())) {
	return false;
	}
	else if(!isRotated && (target < nums.front() || target > nums.back())) {
	return false;
	}
	//> need to search
	if(isRotated) {
	if(target >= nums.front()) {
	for(int i = 0; i < nums.size(); i++) {
	if(nums[i] == target) {
	return true;
	}
	//> skip duplicates
	while(i < nums.size() && nums[i] == nums[i+1]) {
	++i;
	}
	//> reach the end of left half
	if(i < (nums.size() - 1) && nums[i] > nums[i+1]) {
	break;
	}
	}
	}
	else {
	for(int i = nums.size()-1; i >= 0; i--) {
	if(nums[i] == target) {
	return true;
	}
	//> skip duplicates
	while(i > 0 && nums[i] == nums[i-1]) {
	--i;
	}
	//> reach the end of right half
	if(i > 0 && nums[i] < nums[i-1]) {
	break;
	}
	}
	}
	}
	else {
	//> not rotated, use binary seatch
	int left = 0, right = nums.size() - 1;
	while(left <= right) {
	int mid = (left + right) / 2;
	if(nums[mid] == target) {
	return true;
	}
	else if(nums[mid] < target) {
	left = mid + 1;
	}
	else {
	right = mid - 1;
	}
	}
	}
	return false;
	}
	};

view raw searchInRotatedListII.cpp hosted with ❤ by GitHub

也可以只使用 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

	class Solution {
	fun search(nums: IntArray, target: Int): Boolean {
	var left = 0
	var right = nums.lastIndex
	var mid: Int
	while(left <= right) {
	mid = left + (right - left) / 2
	when {
	nums[mid] == target -> return true
	nums[mid] > nums[right] -> { // rotated
	if(nums[left] <= target && target < nums[mid]) {
	right = mid - 1
	} else {
	left = mid + 1
	}
	}
	nums[mid] < nums[right] -> {
	if(nums[mid] < target && nums[right] >= target) {
	left = mid + 1
	} else {
	right = mid - 1
	}
	}
	else -> --right
	}
	}
	return false
	}
	}

view raw search_in_rotated_sorted_array_II.kt hosted with ❤ by GitHub