未分類

Search in Rotated Sorted Array II

Array, BinarySearch, Go, LeetCode

Search in Rotated Sorted Array II

Follow up for “Search in Rotated Sorted Array”:

What if duplicates are allowed?

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

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

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

The array may contain duplicates.

提示 解題應用
Array Array/Slice
BinarySearch BinarySearch

Default:

1
2
3
func search(nums []int, target int) bool {
}

解答思路:

之前有一遍Search in Rotated Sorted Array，其做法是先找出最小值並以此來推算整個array位移了多少格，在沒有重覆值的情況下可以在時間O(logN)的複雜度下完成，但如果是重覆值存在的情況下最糟會需要O(N)的複雜度，而且這次就沒辦法像之前一樣先找出最小值來先得知位移多少格，因為在極端的情況下如果有大量的重覆值出現，而且重覆的值都剛為最小值的話，就算找到最小值的位置也未必代表是原陣列的第一個位置，因此也無法推出位移了多少格，與其這樣倒不如就想辦法直接找目標值，直接透過二分法比較目標值與開頭值、中間值、結尾值來得出目標值是落在開頭到中間的區塊還是落在中間到結尾的區塊，最後透過這樣不斷的篩選來逐步找出結果，當然這樣的方法也適用於前一題之中(沒有重覆值的情況下)。

程式碼解說:

要直接透過二分法的方式來找出目標值的話需要在判斷式上面多下點功夫，一開始頭與尾的初始index值分別為陣列的第一個與與最後一個，並開始以迴圈篩選出目標值存在的範圍直到開頭的index值超過結尾，接著就將開頭與結尾的index相加再除2取得中間的index，如果該中間值為目標值就直接回傳true，到這邊都與基本的二分法一樣，因為接下來要找目標值是落在陣列的前半部還是後半部，這邊先拿中間值與結尾值做比較(要一一分別將目標值與開頭值、中間值、結尾值做比較也行)，如果中間值比結尾值大的話，接著就判斷目標值是不是落在中間值與開頭之間，如果是的話就將結尾的index移動到中間index的前一個(表示落在前半部)，否則則是將開頭的index移動到中間index的下一個(落在後半)，反之如果中間值比結尾值小則情況相反，最後如果是中間值與結尾相等的情況，這個時候就需要將開頭或結尾移動向內移動一格來尋找相異值以繼續做比較，這邊是以移動結尾為主，在迴圈結束之後，還需要再做一次檢查用以對應陣列長度只有0,1,2的情況，而因為陣列長度為1或2的情況下，開頭與結尾的index最後都會相同，因此只要長度大於1就只檢查其中一個即可，如果與目標值相同就回傳true，否則就回傳false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var mid int
front := 0
rear := len(nums) - 1
for front < rear {
	mid = (front + rear) / 2
	if nums[mid] == target {
		return true
	} else if nums[mid] > nums[rear] {
		if nums[mid] > target && nums[front] <= target {
			rear = mid - 1
		} else {
			front = mid + 1
		}
	} else if nums[mid] < nums[rear] {
		if nums[mid] < target && nums[rear] >= target {
			front = mid + 1
		} else {
			rear = mid - 1
		}
	} else {
		rear--
	}
}
if len(nums) > 0 && nums[front] == target {
	return true
}
return false

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func search(nums []int, target int) bool {
	var mid int
	front := 0
	rear := len(nums) - 1
	for front < rear {
		mid = (front + rear) / 2
		if nums[mid] == target {
			return true
		} else if nums[mid] > nums[rear] {
			if nums[mid] > target && nums[front] <= target {
				rear = mid - 1
			} else {
				front = mid + 1
			}
		} else if nums[mid] < nums[rear] {
			if nums[mid] < target && nums[rear] >= target {
				front = mid + 1
			} else {
				rear = mid - 1
			}
		} else {
			rear--
		}
	}
	if len(nums) > 0 && nums[front] == target {
		return true
	}
	return false
}

總結:

陣列中資料有序且包含重覆值的情況下，雖然元素的位置經過位移(旋轉)，但還是能直接透過二分法比較目標值與開頭值、中間值、結尾值來得出目標值是落在開頭到中間的區塊還是落在中間到結尾的區塊，最後透過這樣不斷的篩選來逐步找出結果。

分享到