浙江大学PAT上机例题析之3-05. 求链式线性表的倒数第K项

浙江大学PAT上机题解析之3-05. 求链式线性表的倒数第K项

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

输入格式说明：

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

输出格式说明：

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

样例输入与输出：

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

7

6 3 6 7 8 2 -2

NULL

//注意，这一题，题目很简单，但是可能数据量会很大，如果不用二分来搜索肯定会超时，还有一般遇到这种对时间要求比较高的题目最好使用stdio的输入输出流，比iostream快不少。

#include <cstdio>#include <vector>using namespace std;int main(){int K;vector<int>  vec;vector<int>::iterator left,right,mid;int temp=0;bool flag = true;scanf("%d",&K);while(scanf("%d",&temp),temp>=0)vec.push_back(temp);if (vec.empty()|| K>vec.size()){printf("NULL\n");return 0;}vector<int>::iterator N =vec.begin()+( vec.size()-K);left = vec.begin();right = vec.end()-1;if (left==right){printf("%d\n",*left);return 0;}while(left<=right &&left>=vec.begin()&&left<vec.end()&&right>=vec.begin()&&right<vec.end()){mid = left + (right-left)/2;if (mid==N)  {  printf("%d\n",*mid);  flag = false;  break;  }if (mid>N)right = mid-1;elseif (mid<N)left =  mid+1;}if (flag)printf("NULL\n");//system("pause");return 0;}