给定一个从1 到 n 排序的整数列表。
首先,从左到右,从第一个数字开始,每隔一个数字进行删除,直到列表的末尾。
第二步,在剩下的数字中,从右到左,从倒数第一个数字开始,每隔一个数字进行删除,直到列表开头。
我们不断重复这两步,从左到右和从右到左交替进行,直到只剩下一个数字。
返回长度为 n 的列表中,最后剩下的数字。
示例:
输入: n = 9, 1 2 3 4 5 6 7 8 9 2 4 6 8 2 6 6 输出: 6 Related Topics数学
通过常规方法编写程序,程序运行超时。
int count = 0;
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= n; i++) {
list.add(i);
}
while (true) {
if (list.size() == 1) {
break;
}
if (count % 2 == 0) {
for (int i = 0; i < list.size(); i += 2) {
list.remove(i);
i--;
}
} else {
for (int i = list.size() - 1; i >= 0; i -= 2) {
list.remove(i);
}
}
count += 1;
}
return list.get(0);
思路
提示使用数学进行解答,这里想到的就是使用递归。这里可以获取前面几个值。看能不能找到一些规律。其中f(n) 代表从左面开始的结果。 g(n)代表从右边开始的结果。
f(1) = 1 g(1) = 1
f(2) = 2 g(2) = 1
f(3) = 2 g(3) = 2
f(4) = 2 g(4) = 3
f(5) = 2 g(5) = 4
f(6) = 4 g(6) = 3
f(7) = 4 g(7) = 4
f(8) = 6 g(8) = 3
…… …….
由上面可以得到如下:
结果一:当n = 1 时 结果为 1。
规律一:f(n) + g(n) = n + 1
规律二:f(n) = g(n/2) * 2
由规律一得到:g(n) = n + 1 – f(n) 将该结果代入规律二中:
f(n) = (n/2 +1 – f(n/2)) *2
这样就可以写一个递归
代码:
public int lastRemaining(int n) {
if (n == 1) {
return 1;
} else {
return (n / 2 + 1 - lastRemaining(n / 2)) * 2;
}
}