[leetcode] Find Minimum in Rotated Sorted Array II
发布时间:2020-12-16 18:48:28 所属栏目:大数据 来源:网络整理
导读:code:https://play.golang.org/p/luj1fdu03F problem: https://oj.leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/ package mainimport ( "fmt" "math/rand" "sort" "time")//rotate数组方法一func rotateArray1(a []int,pos int) { if po
code:https://play.golang.org/p/luj1fdu03F package main import ( "fmt" "math/rand" "sort" "time" ) //rotate数组方法一 func rotateArray1(a []int,pos int) { if pos < 0 { return } lenA := len(a) pos = pos % lenA tmpArray := make([]int,pos) for i := 0; i < pos; i++ { tmpArray[i] = a[i] } for i := pos; i < lenA; i++ { a[i-pos] = a[i] } for i := 0; i < pos; i++ { a[lenA-pos+i] = tmpArray[i] } } //rotate数组方法2 func rotateArray2(a []int,pos int) { if pos < 0 { return } lenA := len(a) pos = pos % lenA reverseArray(a[:pos]) reverseArray(a[pos:]) reverseArray(a) } //reverse数组,反转 func reverseArray(a []int) { for i,j := 0,len(a)-1; i < j; i,j = i+1,j-1 { a[i],a[j] = a[j],a[i] } } func main() { len := 20 a := make([]int,len) seedNum := 0 rand.Seed(int64(seedNum) + time.Now().UnixNano()) for i := 0; i < len; i++ { seedNum++ a[i] = rand.Intn(20) } fmt.Println("-------") sort.Ints(a) rotatePos := rand.Intn(len) fmt.Printf("rotate pos:%dn",rotatePos) fmt.Printf("origin array:%vn",a) rotateArray2(a,rotatePos) fmt.Printf("rotated array:%vn",a) //sort.Sort(sort.Reverse(sort.IntSlice(a[]))) fmt.Println(findMin(a)) } func findMin(arrItem []int) int { lenItem := len(arrItem) low := 0 high := lenItem - 1 if arrItem[low] < arrItem[high] { return arrItem[low] } for low < high-1 { mid := (low + high) / 2 if arrItem[low] >= arrItem[high] { if arrItem[mid] < arrItem[low] { high = mid } else { low = mid } } } if arrItem[low] < arrItem[high] { return arrItem[low] } else { return arrItem[high] } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |