topK.js

function topK (n, k, arr1) {
    let x1 = n - 1
    let y1 = n - 1
    let x2 = n - 1
    let y2 = n - 1
    let endX = x1
    let endY = y1
    let arr = [arr1[y1][x1]]

    // 1  2  3  4
    // 5  7  8  9
    // 9  11 12 13
    // 14 16 17 18
    while (arr.length < k) {
        if (arr1[y1-1][x1] > arr1[y2][x2-1]) {
            console.log('right:',arr1[y1-1][x1])
            arr.push(arr1[y1-1][x1])
            --y1
            if (y1 === 0) {
                y1 = endY
                --x1
            }
        } else {
            console.log('left:',arr1[y2][x2-1], y2, x2-1)
            arr.push(arr1[y2][x2-1])
            --x2
            if (x2 === 0) {
                x2 = endX
                --y2
            }
        }
    }
    return arr
}

function topK2 (n, k, arr1) {
    let x1 = n - 1
    let y1 = n - 1
    let x2 = n - 1
    let y2 = n - 1
    let endX = x1
    let endY = y1
    let arr = [] // [arr1[y1][x1]]

    // 1 2 6  8
    // 2 4 8  10
    // 3 5 9  11
    // 4 6 10 12
    let count = arr1.length*arr1.length
    while (arr.length < k) {
        arr.push(arr1[y2][x2])
        if (x2 === 0) {
            if (y2 === 0) break

            --y2
            x2 = arr1.length
        }
        --x2

        // if (arr1[y1-1][x1] > arr1[y2][x2-1]) {
        //     console.log('right:',arr1[y1-1][x1])
        //     arr.push(arr1[y1-1][x1])
        //     --y1
        //     if (y1 === 0) {
        //         y1 = endY
        //         --x1
        //     }
        // } else {
        //     console.log('left:',arr1[y2][x2-1], y2, x2-1)
        //     arr.push(arr1[y2][x2-1])
        //     --x2
        //     if (x2 === 0) {
        //         x2 = endX
        //         --y2
        //     }
        // }
    }
    return arr
}

// let arr1 = [[1, 2, 3, 4], [5, 7, 8, 9], [9, 11, 12, 13], [14, 16, 17, 18]]
let arr1 = [[1,2,6, 8], [2,4,8, 10], [3,5,9, 11], [4,6,10,12]]
// let arr2 = [1, 3, 5, 9, 10]
const result = topK2(4, 80, arr1)
console.log('result:', result)

//     x1  x2  x3  x4  x5
// y1  1+1 1+2 1+3 1+4 1+5
// y2  2+1 2+2 2+3 2+4 2+5
// y3  3+1 3+2 3+3 3+4 3+5
// y4  4+1 4+2 4+3 4+4 4+5
// y5  5+1 5+2 5+3 5+4 5+5

// 1  2  3  4
// 5  7  8  9
// 9  11 12 13
// 14 16 17 18
//
// 1 2 6  8
// 2 4 8  10
// 3 5 9  11
// 4 6 10 12
//
//
// 17 > 13, 16 > 13, 14 > 13, 13
// 12 > 9, 11 > 9, 9 >= 9
// 9>8,