有时,我们会关心相邻名次间成绩的差异,比如冠军与亚军差多少,第四名与第五名差多少等等。编写函数,计算模拟的成绩数组(均为非负整数,但是是无序的)中相邻的名次间成绩的最大差异(指按从高到低排序后,前一名较后一名相差的最大值)。显然,排序后再统计是一种方法,我们对时间效率有一定的要求:你能否在o(n)的时间和空间复杂度下完成该任务?你可以认为,数据数量少于2个时,差异认为是0。
时间: 2023-05-03 09:01:47 浏览: 330
题目的意思是,在计算模拟中,有时我们会关心相邻名次间成绩的差异,比如冠军与亚军差多少,第四名与第五名差多少等等。编写函数,计算模拟的成绩数组(均为非负整数,但是是无序的)中相邻成绩的最大差异(指按从高到低顺序后,前一名与后一名成绩的差异的最大值)。显然,排序后进行一遍扫描就可以轻易解决,但排序的时间复杂度为O(nlogn),不足以满足O(n)的时间要求。你可以认为,数据数量少于2个时,差异认为是0。
阅读全文