AcWing 786. 第k个数 JavaScript
原题链接
简单
作者:
gaobowen
,
2019-11-11 17:44:24
,
所有人可见
,
阅读 618
var buf = '';
process.stdin.on('readable', function () {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
let getInputArgs = line => {
//输入参数有空字符需要去除
return line.split(' ').filter(s => s !== '').map(x => parseInt(x));
}
var arr = [];
function quickSort(l, r, k) {
if (l >= r) return arr[r];
let x = arr[parseInt((l + r) / 2)];
let i = l - 1;
let j = r + 1;
while (i < j) {
do { i++ } while (arr[i] < x);
do { j-- } while (arr[j] > x);
if (i < j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//目标在右侧
if (j < k - 1) {
return quickSort(j + 1, r, k);
}
//目标在左侧 j > k - 1
else {
return quickSort(l, j, k);
}
}
process.stdin.on('end', function () {
let k = 1;
buf.split('\n').forEach(function (line, lineIdx) {
if (lineIdx % 2 === 1) {
arr = getInputArgs(line);
console.log(quickSort(0, arr.length - 1, k));
}
else {
k = getInputArgs(line)[1]
}
});
});