[leetcode] Find Minimum in Rotated Sorted Array II

code：https://play.golang.org/p/luj1fdu03F
problem: https://oj.leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

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]
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!