给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第k个位置上的数字。\n\n输入格式:\n输入首先给出一个正整数k，随后是若干非负整数，最后以一个负整数表示结尾（该负数不算在序列内，不要处理）。\n\n输

### 回答1：
入样例：
3 1 2 3 4 5 6 -1

输出样例：
4

解释：倒数第3个位置上的数字是4。

算法思路：
可以使用双指针法，让一个指针先走k步，然后两个指针同时走，当先走的指针到达末尾时，后走的指针所指的数字就是倒数第k个位置上的数字。

代码实现：

### 回答2：
题分析：
此题要求找到从序列末尾开始的第k个数字。考虑用一个指针记录序列长度，每读入一个数就将指针加一。当指针大于k时，就将指针前移一位，将第一个输入的数丢掉，等到指针移动到末尾时，当前指向的数就是倒数第k个。但这样做效率太低，需要移动整个序列，复杂度为O(n)，无法通过所有测试数据。因此，我们需要更高效的算法。

算法设计：
我们可以用一个大小为k的辅助数组来存储最近读入的k个非负整数。当输入一个新的数时，将其插入到这个数组的尾部，同时将数组的头部删除。当输入负整数时，直接退出输入循环。这样，在读入输入时，我们可以保证辅助数组中一直存储着最新的k个非负整数。当输入结束后，我们只需要输出辅助数组的头部即可得到倒数第k个数字。

算法分析：
该算法的时间复杂度为O(k)，空间复杂度也为O(k)，非常高效。而且，由于只需要处理输入的整数，没有额外的计算操作，因此非常适合在输入数据流不断产生的场合下使用。

算法实现：
下面给出该算法的代码实现，其中的len表示当前辅助数组中存储的数字个数：

k = int(input())
num_list = []
len = 0
while True:
    num = int(input())
    if num < 0:
        break
    num_list.append(num)
    len += 1
    if len > k:
        num_list.pop(0)
        len -= 1
print(num_list[0])

总体而言，该算法时间复杂度低，易于实现，是寻找倒数第k个数字的一种高效方法。

### 回答3：
题分析：

该题目要求我们找到一个长为n的数组的倒数第K个位置的数。一个可行的算法可以是用快慢指针的方法。定义两个指针p, q 。p指向数组第k个位置，q指向数组第一个位置。当p向前移动k-1次之后，p和q开始同时向前走，直到p到达数组结尾。此时q指向的位置就是倒数第k个数字。

代码实现：

我们可以在读入数组的同时用一个counter记录数组的大小n和找到k位置。我们不需要保存整个数组，只需要移动p和q指针，找到答案即可。时间复杂度为$O(n)$。

代码如下：

k = int(input())
a = []
counter = 0
while True:
    num = int(input())
    if num < 0:
        break
    a.append(num)
    counter += 1

p, q = a[k-1], a[0]
for i in range(k-1):
    q = a[i]

while p != a[-1]:
    p = a[a.index(p) + 1]
    q = a[a.index(q) + 1]
print(q)

示例：

输入：

2
3 6 7 1 4 2 8 3 0 -1

输出：

8