1-6 求链式线性表的倒数第K项 (20 分)

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

输入格式:

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

输出格式:

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

输入样例:

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

输出样例:

7

 题目打算用链表，但我觉得数组直接就能拿来用...

肯定会有大数据，卡超时卡内存。再大的数组直接用都不够

所以知道输出倒数第k个，那就整一个大小为K的就刚刚够用了。循环存储，转着圈的存....

while(1){
    for(i=0;i<n;i++){
        cin>>k;
        if(k>0){
            count++;
            num[i]=k;

}

然后输出的时候输出 i前面那个刚好就是转了一圈，也就是退回了K个。

 

AC代码

#include<iostream>
#include<vector>
using namespace std;
int main(){
	int n;
	cin>>n;
	vector<int>num(n);
	int i=0,k,count=0;
	while(1){
	for(i=0;i<n;i++){
		cin>>k;
		if(k>0){
			count++;
			num[i]=k;
		}else{
			if(count<n){
				cout<<"NULL";
			}
			else{
			cout<<num[(i+1)%n];
			}
			return 0;
		}
	}
	}
	return 0;
}

这样学数据结构不太厚道...后面再写一个用链表做的吧