目錄

153. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 Find Minimum In Rotated Sorted Array??????

154. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 II Find Minimum In Rotated Sorted Array II????????

?? 每日一練刷題專欄???

Golang每日一練 專欄

Python每日一練 專欄

C/C++每日一練 專欄

Java每日一練 專欄

153. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 Find Minimum In Rotated Sorted Array

已知一個(gè)長度為?n?的數(shù)組，預(yù)先按照升序排列，經(jīng)由?1?到?n?次?旋轉(zhuǎn)?后，得到輸入數(shù)組。例如，原數(shù)組?nums = [0,1,2,4,5,6,7]?在變化后可能得到：

• 若旋轉(zhuǎn)?4?次，則可以得到?[4,5,6,7,0,1,2]
• 若旋轉(zhuǎn)?7?次，則可以得到?[0,1,2,4,5,6,7]

注意，數(shù)組?[a[0], a[1], a[2], ..., a[n-1]]?旋轉(zhuǎn)一次?的結(jié)果為數(shù)組?[a[n-1], a[0], a[1], a[2], ..., a[n-2]]?。

給你一個(gè)元素值?互不相同?的數(shù)組?nums?，它原來是一個(gè)升序排列的數(shù)組，并按上述情形進(jìn)行了多次旋轉(zhuǎn)。請你找出并返回?cái)?shù)組中的?最小元素?。

你必須設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為?O(log n)?的算法解決此問題。

示例 1：

輸入：nums = [3,4,5,1,2]
輸出：1
解釋：原數(shù)組為 [1,2,3,4,5] ，旋轉(zhuǎn) 3 次得到輸入數(shù)組。

示例 2：

輸入：nums = [4,5,6,7,0,1,2]
輸出：0
解釋：原數(shù)組為 [0,1,2,4,5,6,7] ，旋轉(zhuǎn) 4 次得到輸入數(shù)組。

示例 3：

輸入：nums = [11,13,15,17]
輸出：11
解釋：原數(shù)組為 [11,13,15,17] ，旋轉(zhuǎn) 4 次得到輸入數(shù)組。

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums?中的所有整數(shù)?互不相同
• nums?原來是一個(gè)升序排序的數(shù)組，并進(jìn)行了?1?至?n?次旋轉(zhuǎn)

代碼：

package main

import "fmt"

func findMin(nums []int) int {
	n := len(nums)
	left, right := 0, n-1
	for left < right {
		mid := left + (right-left)/2
		if nums[mid] < nums[right] {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return nums[left]
}

func main() {
	nums := []int{3, 4, 5, 1, 2}
	fmt.Println(findMin(nums))
	nums = []int{4, 5, 6, 7, 0, 1, 2}
	fmt.Println(findMin(nums))
	nums = []int{11, 13, 15, 17}
	fmt.Println(findMin(nums))
}

輸出：

1
0
11?

154. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 II Find Minimum In Rotated Sorted Array II

已知一個(gè)長度為?n?的數(shù)組，預(yù)先按照升序排列，經(jīng)由?1?到?n?次?旋轉(zhuǎn)?后，得到輸入數(shù)組。例如，原數(shù)組?nums = [0,1,4,4,5,6,7]?在變化后可能得到：

• 若旋轉(zhuǎn)?4?次，則可以得到?[4,5,6,7,0,1,4]
• 若旋轉(zhuǎn)?7?次，則可以得到?[0,1,4,4,5,6,7]

注意，數(shù)組?[a[0], a[1], a[2], ..., a[n-1]]?旋轉(zhuǎn)一次?的結(jié)果為數(shù)組?[a[n-1], a[0], a[1], a[2], ..., a[n-2]]?。

給你一個(gè)可能存在?重復(fù)?元素值的數(shù)組?nums?，它原來是一個(gè)升序排列的數(shù)組，并按上述情形進(jìn)行了多次旋轉(zhuǎn)。請你找出并返回?cái)?shù)組中的?最小元素?。

你必須盡可能減少整個(gè)過程的操作步驟。

示例 1：

輸入：nums = [1,3,5]
輸出：1

示例 2：

輸入：nums = [2,2,2,0,1]
輸出：0

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums?原來是一個(gè)升序排序的數(shù)組，并進(jìn)行了?1?至?n?次旋轉(zhuǎn)

進(jìn)階：這道題與上一題154.類似，但?nums?可能包含重復(fù)元素。允許重復(fù)會影響算法的時(shí)間復(fù)雜度嗎？會如何影響，為什么？

代碼：

package main

import "fmt"

func findMin(nums []int) int {
	n := len(nums)
	left, right := 0, n-1
	for left < right {
		mid := left + (right-left)/2
		if nums[mid] < nums[right] {
			right = mid
		} else if nums[mid] > nums[right] {
			left = mid + 1
		} else {
			right--
		}
	}
	return nums[left]
}

func main() {
	nums := []int{1, 3, 5}
	fmt.Println(findMin(nums))
	nums = []int{2, 2, 2, 0, 1}
	fmt.Println(findMin(nums))
	nums = []int{4, 5, 6, 7, 0, 1, 4}
	fmt.Println(findMin(nums))
}

輸出：

1
0
0

思路：

與第 153 題類似，在找到中間元素時(shí)，需要考慮以下兩種情況：

1. nums[mid] < nums[right]：說明最小值在左側(cè)，將右端點(diǎn)更新為 mid；

2. nums[mid] > nums[right]：說明最小值在右側(cè)，將左端點(diǎn)更新為 mid + 1。

如果 nums[mid] == nums[right]，則無法判斷最小值在哪一側(cè)，此時(shí)將右端點(diǎn)減一。

?? 每日一練刷題專欄???

? 持續(xù)，努力奮斗做強(qiáng)刷題搬運(yùn)工！

?? 點(diǎn)贊，你的認(rèn)可是我堅(jiān)持的動力！?

???收藏，你的青睞是我努力的方向！?

? 評論，你的意見是我進(jìn)步的財(cái)富！??

??主頁：https://hannyang.blog.csdn.net/?文章來源地址http://www.zghlxwxcb.cn/news/detail-431163.html

	Golang每日一練 專欄
	Python每日一練 專欄
	C/C++每日一練 專欄
	Java每日一練 專欄

到了這里，關(guān)于Golang每日一練(leetDay0052)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！