find_minimum_in_rotated_sorted_array_II

hitzzc · hitzzc · commit 7e1bb67831fc · 2016-10-14T18:32:32.000+08:00
diff --git a/README.md b/README.md
@@ -137,6 +137,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [151. reverse words in a string](https://github.com/hitzzc/go-leetcode/tree/master/reverse_words_in_a_string)
 #### [152. maximum product subarray](https://github.com/hitzzc/go-leetcode/tree/master/maximum_product_subarray)
 #### [153. find minimum in rotated sorted array](https://github.com/hitzzc/go-leetcode/tree/master/find_minimum_in_rotated_sorted_array)
+#### [154. find minimum in rotated sorted array II](https://github.com/hitzzc/go-leetcode/tree/master/find_minimum_in_rotated_sorted_array_II)
 
 
 
diff --git a/find_minimum_in_rotated_sorted_array_II/find_minimum_in_rotated_sorted_array_II.go b/find_minimum_in_rotated_sorted_array_II/find_minimum_in_rotated_sorted_array_II.go
@@ -0,0 +1,29 @@
+package find_minimum_in_rotated_sorted_array_II
+
+func findMin(nums []int) int {
+	return helper(nums, 0, len(nums)-1)
+}
+
+func helper(nums []int, left, right int) int {
+	if left == right {
+		return nums[left]
+	}
+	if nums[left] < nums[right] {
+		return nums[left]
+	}
+	mid := left + (right-left)/2
+	if mid == left {
+		return helper(nums, left+1, right)
+	}
+	if nums[left] == nums[mid] && nums[mid] == nums[right] {
+		for ; left < right && nums[left] == nums[left+1]; left++ {
+		}
+		for ; left < right && nums[right] == nums[right-1]; right-- {
+		}
+		return helper(nums, left, right)
+	}
+	if nums[left] <= nums[mid] && nums[mid] > nums[right] {
+		return helper(nums, mid+1, right)
+	}
+	return helper(nums, left, mid)
+}
