python进阶编程_3_最大数,最小数的统计

心已赠人 2022-05-28 01:09 127阅读 0赞

时间限制：1秒

空间限制：32768K

小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，差最小的有多少对呢？差最大呢？

##### 输入描述: #####

输入包含多组测试数据。 对于每组测试数据： N - 本组测试数据有n个数 a1,a2...an - 需要计算的数据 保证: 1<=N<=100000,0<=ai<=INT\_MAX.

##### 输出描述: #####

对于每组数据，输出两个数，第一个数表示差最小的对数，第二个数表示差最大的对数。

##### 输入例子1: #####

6
    45 12 45 32 5 6

##### 输出例子1: #####

1 2

# -*- coding: utf-8 -*-  
    def f(nums, N):  
        _min, _max = nums[0], nums[-1]# nums最大值和最小值  
        #极端情况，所有数字都一样  
        if _min == _max:  
            return str(N*(N-1)/2) + ' ' + str(N*(N-1)/2)       
        ret_max, ret_min = 0, 0# 返回值参数  
           
        #寻找最大差值对数  
        ret_max = nums.count(_min) * nums.count(_max)# 最大差值对数  
           
        #寻找最小差值对数 ,非零的情况,将每出现结果为最小的差值更新,每重复一次值加一
        min_dif = float('inf')# 最小差值初始化维正无穷  
        for i in range(N-1):# 循环寻找最小差值对数，ret_min表示最小差值对数  
            diff = nums[i+1] - nums[i]  
            if diff < min_dif:  
                ret_min = 1  
                min_dif = diff  
            elif diff == min_dif:  
                ret_min += 1
        #上式判断代码只能保证非零差值的统计,一旦差值结果为0,
        #则必须将每一阶段差值为0分开讨论而且还要重新组合统计
        # 极端情况，存在差值为0，这时需要重新判断  
        if min_dif == 0:  
            count = 0  #用于统计当前排列小段中大小相等的元素的个数
            ret_min = 0  
            for i in range(N-1):  
                if nums[i+1] == nums[i]:  
                    count += 1  
                else:  
                    if count > 0:# 因为上面count初始值为0，因此实际上count应该再+1
                        #count=count+1
                        #ret_min+=count*(count-1)/2
                        ret_min += count*(count+1)/2#从count个数选出2个  
                        count = 0  
            #在最后的一小段中
            #可能一直是nums[i+1] == nums[i]，没有else，因此还需要在加一个  
            #如果count=0则不影响最后结果  
            ret_min += count*(count+1)/2  
            ret_min=int(ret_min)
        return str(ret_min) + ' ' + str(ret_max)  
    
    if __name__ == '__main__':  
        while 1:  
            try:  
                N =int( input()  )
                nums = list(map(int,input().strip().split()) )
            except:  
                break  
            nums.sort()  
            print (f(nums, N) )