TypeScript / JavaScript 实现 LeetCode 3782 lastInteger

题意回顾

初始数组 [1,2,3,...,n] ，交替执行删除：

1. 第一轮：从左删，隔一删一（保留奇数位置）
2. 第二轮：从右删，隔一删一
循环直到只剩一个数，返回结果
数据极大（1e15），不能模拟数组，用迭代 O(logn) 最优解法

迭代 O(logn) 版本（无递归，大数安全）

typescript
function lastInteger(n: number): number {
let start = 1;
let end = n;
let step = 1;
let remain = n;

while (remain > 1) {
// 从左侧删除一轮
if (remain % 2 === 1) {
end -= step;
}
// 切换为从右侧删：翻转区间，步长取反翻倍
[start, end] = [end, start];
step *= -2;
remain = Math.floor((remain + 1) / 2);
}
return start;
}


递归简洁版（逻辑直观，n极大时栈深很小）AC

typescript
function lastInteger(n: number): number {
if (n === 1) return 1;
const m = Math.floor((n + 1) / 2);
return 2 * (m + 1 - lastInteger(m)) - 1;
}


JS 原生版本（去掉类型标注，浏览器/Node直接运行）

javascript
function lastInteger(n) {
let start = 1, end = n, step = 1, remain = n;
while (remain > 1) {
if (remain % 2 === 1) end -= step;
[start, end] = [end, start];
step *= -2;
remain = (remain + 1) >> 1;
}
return start;
}


测试样例

typescript
console.log(lastInteger(1)); // 1
console.log(lastInteger(5)); // 1
console.log(lastInteger(8)); // 3


复杂度

- 时间：O(\log n)，每次数量折半
- 空间：迭代版 O(1)，递归版 O(\log n)