414. 第三大的数

414. 第三大的数

堆排序

package main
import (
    "container/heap"
    "fmt"
    "sort"
)
type IntList []int
func (l IntList)Len()int{
    return len(l)
}
func(l IntList)Swap(i,j int){
    l[i],l[j] = l[j],l[i]
}
func(l IntList) Less(i, j int) bool{
    return l[i]<l[j]
}
func (l *IntList)Push(x interface{}){
    *l = append(*l,x.(int))
}
func (l *IntList)Pop()interface{}{
    x := (*l)[len(*l)-1]
    *l = (*l)[:len(*l)-1]
    return x
}
func thirdMax(nums []int) int {
    sort.Ints(nums)
    list := make(IntList,0)
    m :=make(map[int]struct{})
    heap.Init(&list)
    for i :=0;i<len(nums);i++{
        if _,ok:=m[nums[i]];!ok{
            heap.Push(&list,nums[i])
            m[nums[i]]= struct {}{}
        }
    }
    if len(list)<3 {
        return list[len(list)-1]
    }
    return list[len(list)-3]
}
func main() {
    fmt.Println(thirdMax([]int{3,2,1}))//1
    fmt.Println(thirdMax([]int{1,2}))//2
    fmt.Println(thirdMax([]int{2,2,3,1}))//1
    fmt.Println(thirdMax([]int{1,2,2,5,3,5}))//2
    fmt.Println(thirdMax([]int{1,-2147483648,2}))//-2147483648
    fmt.Println(thirdMax([]int{1,2,-2147483648}))//-2147483648
}

func thirdMax(nums []int) int {
    //sort.Ints(nums)
    //list := make(IntList,0)
    m :=make(map[int]struct{})
    //heap.Init(&list)
    var list []int
    for i :=0;i<len(nums);i++{
        if _,ok:=m[nums[i]];!ok{
            list =append(list,nums[i])
            m[nums[i]]= struct {}{}
        }

    }
    heapSort(list)
    if len(list)<3 {
        return list[0]
    }
    return list[2]
}

func heapSort(input []int){
    inputLen := len(input)
    if inputLen == 0 {
        return
    }
    for i:=0; i<inputLen; i++{
        minAjust(input[i:])
    }
}

func minAjust(input []int){
    inputLen := len(input)
    if inputLen <= 1{
        return
    }
    for i:= inputLen/2 -1; i>=0; i--{
        if (2*i+1 <= inputLen-1) && (input[i] <= input[2*i+1]){
            input[i], input[2*i+1] = input[2*i+1], input[i]
        }
        if (2*i+2<= inputLen-1) && (input[i] <= input[2*i+2]){
            input[i], input[2*i+2] = input[2*i+2], input[i]
        }
    }
}


func main() {
    fmt.Println(thirdMax([]int{3,2,1}))//1
    fmt.Println(thirdMax([]int{1,2}))//2
    fmt.Println(thirdMax([]int{2,2,3,1}))//1

    fmt.Println(thirdMax([]int{1,2,2,5,3,5}))//2
    fmt.Println(thirdMax([]int{1,-2147483648,2}))//-2147483648
    fmt.Println(thirdMax([]int{1,2,-2147483648}))//-2147483648

    //nums1 :=[]int{1,-2147483648,2}
    //heapSort(nums1)
    //fmt.Println(nums1)
    //nums2 :=[]int{1,2,-2147483648}
    //heapSort(nums2)
    //fmt.Println(nums2)
}