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

可以使用双指针来解决此问题。首先使用一个快指针向前移动k个位置，然后再使用一个慢指针与快指针一起向前移动，直到快指针到达序列末尾。此时慢指针指向的位置就是倒数第k个位置。

具体实现如下：

k = int(input())
nums = []
while True:
    num = int(input())
    if num < 0:
        break
    nums.append(num)

n = len(nums)
if k > n:
    print("NULL")
else:
    fast, slow = k, 0
    while fast < n:
        fast += 1
        slow += 1
    print(nums[slow])

时间复杂度为O(n)，空间复杂度为O(n)。

相关问题

给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第k个位置上的数字

假设给定的正整数序列为a1, a2, ..., an，倒数第k个位置指的是从序列末尾往前数第k个位置，也就是第n-k+1个位置。

一种简单的做法是先遍历一遍序列，确定序列的长度n，然后再遍历一遍序列找到第n-k+1个位置的数。这种做法的时间复杂度为O(n)，并不是最优的。

更高效的做法是使用双指针。首先让一个指针p1从序列开头向前移动k-1个位置，然后再让另一个指针p2从序列开头开始和p1一起向前移动，直到p1到达序列末尾为止。此时p2所指的位置就是倒数第k个位置。这种做法的时间复杂度为O(n)，但是实际上只需要遍历一次序列，所以速度会比上一种做法快很多。

给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第K个位置上的数字。

算法思路：

1.先求出给定正整数的位数n。

2.倒数第K个位置上的数字即为正数第n-K+1个位置上的数字。

3.将给定正整数从左往右数的每一位数字存入一个数组中。

4.输出数组中第n-K+1个位置上的数字即可。

算法实现：

C++代码如下：

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for(int i = 0; i < n; i++)
        cin >> nums[i];
    cout << nums[n-k] << endl;
    return 0;
}

Python代码如下：

n, k = map(int, input().split())
nums = list(map(int, input().split()))
print(nums[n-k])