一道面试算法题目

最近有朋友去面试, 碰到一些算法题目, 我觉得挺有意思, 做个记录.

题目:
- 查找一个无序整数组内, 按照从小到大顺序, 返回“连续”第n大数字的下标.
- 例如 {1, 3, 5, 5, 2, 11, 2, 4}, 5. 表示从数组中找出连续第5大的元素, 则返回下标7
- 例如 {1, 3, 2, 4, 100, 5}, 5. 返回下标5.

直接上代码吧:

package main

import "fmt"

func GetCon(arrs []int, num int) int {
    if len(arrs) == 0 {
        return -1
    }

    if num <= 1 {
        return -1
    }

    mp := map[int]int{} // 这里的k是arr里面的数, value是每个数连续的数量

    for k, v := range arrs {
        preValue := v - 1 // 通过上个元素的连续数量, 知道当前的
        if preNum, ok := mp[preValue]; ok {
            curNum := preNum + 1
            mp[v] = curNum
            if curNum >= num {
                return k
            }

            nextValue := v + 1 // 同时也要衔接后面的元素
            nextConNum := curNum + 1
            for {
                if _, ok := mp[nextValue]; ok {

                    mp[nextValue] = nextConNum
                    if nextConNum >= num {
                        return k
                    }

                    nextValue++
                    nextConNum++
                } else {
                    break
                }
            }
        } else {
            mp[v] = 1
        }
    }

    return -1
}

func main() {
    index := GetCon([]int{1, 3, 5, 5, 2, 11, 2, 4}, 5)
    fmt.Println("index:", index)

    nums := []int{1, 3, 5, 7, 2, 11, 9, 4, 3, 2, 5, 6, 1, 7}
    ret := GetCon(nums, 5)
    // fmt.Println(ret)
    if ret != 7 {
        panic("Algorithm logic error")
    } else {
        fmt.Println("index:", ret)
    }

    nums = []int{1, 2, 3, 4, 5, 100, 6, 7}
    ret = GetCon(nums, 7)
    // fmt.Println(ret)
    if ret != 7 {
        panic("Algorithm logic error")
    } else {
        fmt.Println("index:", ret)
    }

    nums = []int{1, 3, 2, 4, 100, 5}
    ret = GetCon(nums, 5)
    // fmt.Println(ret)
    if ret != 5 {
        panic("Algorithm logic error")
    } else {
        fmt.Println("index:", ret)
    }

    nums = []int{1, 3, 2, 4, 100, 101, 5}
    ret = GetCon(nums, 5)
    // fmt.Println(ret)
    if ret != 6 {
        panic("Algorithm logic error")
    } else {
        fmt.Println("index:", ret)
    }

}