题解 | #第k小数#

package main

import (
    "bufio"
    . "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)

//Scanner在初始化的时候有设置一个maxTokenSize
//这个值默认是MaxScanTokenSize = 64 * 1024 ，
//当一行的长度大于64*1024即65536之后，就会出现ErrTooLong错误。

func findKth(arr []int, l, r, k int) int {
    L, R, i := l-1, r+1, l
    x := arr[l+(r-l)/2]
    // partition
    for i != R {
        if arr[i] < x {
            L++
            arr[i], arr[L] = arr[L], arr[i]
            i++
        } else if arr[i] > x {
            R--
            arr[i], arr[R] = arr[R], arr[i]
        } else {
            i++
        }
    }
    if k <= L {
        return findKth(arr, l, L, k)
    } else if k >= R {
        return findKth(arr, R, r, k)
    }
    return arr[k]
}

// https://ac.nowcoder.com/acm/problem/207028
func NC207028(_r io.Reader, _w io.Writer) {
    in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
    defer out.Flush()

    firstLine, _ := in.ReadString('\n')
    firstLine = strings.TrimSpace(firstLine)
    T, _ := strconv.Atoi(firstLine)
    for T > 0 {
        var n, k int
        secondStr, _ := in.ReadString('\n')
        secondStr = strings.TrimSpace(secondStr)
        secondLine := strings.Split(secondStr, " ")
        n, _ = strconv.Atoi(secondLine[0])
        k, _ = strconv.Atoi(secondLine[1])

        arr := make([]int, n)
        thirdStr, _ := in.ReadString('\n')
        thirdStr = strings.TrimSpace(thirdStr)
        thirdLine := strings.Split(thirdStr, " ")
        for i := 0; i < n; i++ {
            arr[i], _ = strconv.Atoi(thirdLine[i])
        }
        Fprintln(out, findKth(arr, 0, n-1, k-1))
        T--
    }
}

func main() {
    NC207028(os.Stdin, os.Stdout)
}