腾讯笔试题目

2022-02-23 08:42 120阅读 0赞

1、\*\*\*\*  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]  
解析：先说思路：  
首先判断给出的多维数组的个数，如果数组中个数为1，直接跳出（因为无法组成二维数组），如果给出的数组为2，则最大间隔数量=最小间隔数量=1  
如果给出的数组间隔大于2：  
先将列表排序  
1、如果列表中存在重复值  
最小间隔肯定为0，这时统计每个元素出现的个数，并将对于元素出现次数大于2的元素（重复元素）利用公式 重复次数\*（重复次数-1）/2=最小间隔出现次数  
最大间隔出现次数：最小元素出现的次数\*最大元素出现的次数  
2、如果列表中不存在重复值  
最小间隔个数：最小间隔肯定为第i个元素与第i+1个元素的差值中的最小值，这时通过遍历求出差值，形成差值列表，统计差值列表中最小元素的个数  
最大间隔个数：最大值-最小值==1  
注：这道题的时间复杂度不能高于O(N^2 )，也就是说暴力法：找出所有二维数组，计算差值，并找出其中的最大最小值是行不通的，或者在列表中有重复值进行最小间隔个数计算时：先遍历去重后的列表，计算列表中的每个元素的出现的次数，这时我们发现，遍历的时间复杂度为o(n),而count的时间复杂度也为o(n),所以两者加起来的时间复杂度为O(N\*\*2)。所以在进行这一步计算时，最好将其转化为统计每个数字出现次数的列表。  
代码：

from collections import Counter
    while True:
        try:
            n=int(input())
            list1=input().split()
            list1=[int(i) for i in list1]
            if len(list1)!=n:
                break
            if n<0 and n>=100000:
                break
            elif n>=0 and n<2:
                print(0,0)
            elif n==2:
                print(1,1)
            else: #n>3
                result=0
                list1.sort()
                #print(list1)
                if len(set(list1))!= len(list1): #有重复元素时，找出最小间隔个数
                    dict1=Counter(list1)
                    result=0
                    for i in dict1.keys():
                        result=result+dict1[i]*(dict1[i]-1)/2
                    min_gap_num=int(result)
                    #print(min_gap_num)
                    """for i in set(list2):
                        if list1.count(i)>=2:
                            dup_num_i=list1.count(i)
                            result=result+dup_num_i*(dup_num_i-1)/2
                    min_gap_num=result"""
                        
                else:
                    min_gap=[]
                    for i in range(len(list1)-1):
                        min_gap.append(abs(list1[i+1]-list1[i]))
                    #print(min_gap_num)
                    min_gap_num=min_gap.count(min(min_gap))
                if len(set(list1))!=len(list1):#有重复元素，找出最大间隔个数
                    min_dup=list1.count(min(list1))
                    max_dup=list1.count(max(list1))
                    max_gap_num=min_dup*max_dup
                    #print(max_gap_num)
                else:
                    max_gap_num=1
                    #print(max_gap_num)
                print(int(min_gap_num),int(max_gap_num))
        except:
            break

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]: /images/20220223/76e8918a0f694ab2a80a76e720b9d268.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]: /images/20220223/c85d5c1a1e1c459e834fcad93e86bf3e.png