PTA 7-19 求链式线性表的倒数第K项测试点一过不了

Question

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

输入格式:
输入首先给出一个正整数K，随后是若干非负整数，最后以一个负整数表示结尾（该负数不算在序列内，不要处理）。

输出格式:
输出倒数第K个位置上的数据。如果这个位置不存在，输出错误信息NULL。

输入样例:
4 1 2 3 4 5 6 7 8 9 0 -1
输出样例:
7

#include <iostream>
#include <vector>
using namespace std;
main()
{
    int k;
    vector<int> s;
    int x,t=0;
    cin>>k;
    while(1)
    {
        cin>>x;
        if(x<0)
            break;
        s.push_back(x); 
        t++;
    }
    if(t<x)
        cout<<"NULL";
       else
           cout<<s[t-k];
}

这个测试点为啥过不了啊，有没有大lao帮我解答一下

Answer 1

【以下回答由 GPT 生成】

这段代码的问题在于，它使用了一个变量t来记录输入序列的长度，然后在判断t是否小于k的时候输出"NULL"。但是在实际情况下，t记录的是输入序列的长度，并不等于输入的负整数个数，也就是说不能直接用t进行判断。同时，该代码还需要遍历整个序列来找到倒数第k个数字，性能较低。下面是我给出的优化解决方案：

1. 首先修改输入部分的代码，将负整数判断放在循环的条件中，这样可以避免将负整数纳入序列中：

int k;
vector<int> s;
int x;
cin >> k;
while (cin >> x && x >= 0)
{
    s.push_back(x);
}

1. 接下来判断输入序列的长度与k的关系，如果长度小于k，则输出"NULL"：

if (s.size() < k)
{
    cout << "NULL";
}

1. 最后输出倒数第k个数字，由于数组的下标是从0开始的，因此获取倒数第k个数字的下标是s.size() - k。

else
{
    cout << s[s.size() - k];
}

完整的代码如下：

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int k;
    vector<int> s;
    int x;
    cin >> k;

    while (cin >> x && x >= 0)
    {
        s.push_back(x);
    }

    if (s.size() < k)
    {
        cout << "NULL";
    }
    else
    {
        cout << s[s.size() - k];
    }

    return 0;
}

请尝试执行优化后的代码，并检查是否能正确输出结果。

【相关推荐】

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7657580

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^