给定一系列正整数,请设计一个尽可能高效的算法,查找倒数第K个位置上的数字。
输入格式说明:
输入首先给出一个正整数K,随后是若干正整数,最后以一个负整数表示结尾(该负数不算在序列内,不要处理)。
输出格式说明:
输出倒数第K个位置上的数据。如果这个位置不存在,输出错误信息“NULL”。
样例输入与输出:
序号 | 输入 | 输出 |
1 |
4 1 2 3 4 5 6 7 8 9 0 -1 |
7 |
2 |
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;
else
if (mid<N)
left = mid+1;
}
if (flag)
printf("NULL\n"); //system("pause"); return 0;
}
浙江大学PAT上机题解析之3-05. 求链式线性表的倒数第K项的更多相关文章
-
浙江大学PAT上机题解析之1014. 福尔摩斯的约会 (20)
1014. 福尔摩斯的约会 (20) 时间限制 50 ms 内存限制 32000 kB 代码长度限制 8000 B 判题程序 Standard 作者 CHEN, Y ...
-
浙江大学PAT上机题解析之1015. 德才论 (25)
宋代史学家司马光在<资治通鉴>中有一段著名的“德才论”:“是故才德全尽谓之圣人,才德兼亡谓之愚人,德胜才谓之君子,才胜德谓之小人.凡取人之术,苟不得圣人,君子而与之,与其得小人,不若得愚人 ...
-
浙江大学PAT上机题解析之5-05. QQ帐户的申请与登陆
实现QQ新帐户申请和老帐户登陆的简化版功能.最大挑战是:据说现在的QQ号码已经有10位数了. 输入格式说明: 输入首先给出一个正整数N(<=105),随后给出N行指令.每行指令的格式为:“命令符 ...
-
浙江大学PAT上机题解析之2-11. 两个有序链表序列的合并
已知两个非降序链表序列S1与S2,设计函数构造出S1与S2的并集新非降序链表S3. 输入格式说明: 输入分2行,分别在每行给出由若干个正整数构成的非降序序列,用-1表示序列的结尾(-1不属于这个序列) ...
-
浙江大学PAT上机题解析之3-04. 一元多项式的乘法与加法运算
设计函数分别求两个一元多项式的乘积与和. 输入格式说明: 输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000的整数).数字间以空格分 ...
-
浙江大学PAT上机题解析之2-06. 数列求和
给定某数字A(1<=A<=9)以及非负整数N(0<=N<=100000),求数列之和S = A + AA + AAA + … + AA…A(N个A).例如A=1, N=3时,S ...
-
PAT甲题题解-1029. Median (25)-求两序列的中位数,题目更新了之后不水了
这个是原先AC的代码,但是目前最后一个样例会超内存,也就是开不了两个数组来保存两个序列了,意味着我们只能开一个数组来存,这就需要利用到两个数组都有序的性质了. #include <iostrea ...
-
c++刷题(27/100)反转单项链表,链表的倒数第k个
题目1:调整数组顺序使奇数位于偶数前面 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位 ...
-
ocp 1Z0-051 23-70题解析
23. Examine thestructure proposed for the TRANSACTIONS table: name Null Type TRANS_ID NOT NULLNUMBER ...
随机推荐
-
加密配置文件(App.Config和Web.config)中connectionStrings通用方法
1. 背景:根据项目的要求,需要对配置文件配置的数据库连接字符串进行加密,也就是对ConnectinString节点的内容进行加密存储,同时考虑到代码使用连接字符串不需要进行更改,C#会自动对加密的内 ...
-
jQuery 循环问题
$("#add2sub").click(function(){ var $sxarr=$(".add_shuxing_ul > .sx_add_bg"); ...
-
浅析Spring中的注解
Spring的配置,通常有两种:使用配置文件和注解.那么Spring如何知道各个Bean或者Service.Controller以及Bean中各类属性之间的关系呢?答案肯定是在定义各个Java文件的时 ...
-
js动画性能提升笔记
JavaScript动画的性能并不亚于CSS动画.因此,如果使用了现代的动画库,例如Velocity,那么动画引擎的性能将不再是app的瓶颈,构成瓶颈的只有代码. 网络性能相关 动画是浏览器运行中资源 ...
-
[REFERENCE] Real-Time-Normal-Map-Dxt-Compression
DXT5N & 3Dc(aka BC5) compression in common code & SIMD: http://mrelusive.com/publications/pa ...
-
hdu To and Fro
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1200 代码: #include <stdio.h> #include <string ...
-
[Q]自定义纸张大小
问:当打印机纸张列表里没有符合要求的纸张大小,例如如何打印加长图?答:当打印非标准图框时,你可能在图纸列表里找不到想要纸幅.你需要自己新建你需要的纸幅,以pdfFactory虚拟打印机为例(其它打印机 ...
-
bzoj:1675 [Usaco2005 Feb]Rigging the Bovine Election 竞选划区
Description It's election time. The farm is partitioned into a 5x5 grid of cow locations, each of wh ...
-
Linux Supervisor的安装与使用入门
在linux或者unix操作系统中,守护进程(Daemon)是一种运行在后台的特殊进程,它独立于控制终端并且周期性的执行某种任务或等待处理某些发生的事件.由于在linux中,每个系统与用户进行交流的界 ...
-
Windows平台下,Java性能分析工具VisualVM的Tomcat8的配置
VisualVM在JDK6版本及以上已经自带这个应用. 位置:C:\Program Files (x86)\Java\jdk1.8.0_60\bin\jvisualvm.exe 在Windows环 ...