8.8美团笔试算法题

4道编程80分，3道多选20分，感觉凉凉，过来分享一下编程做法：

1、一组数据有n个数字，每个数字范围在[1,n]，输入一个整数k，找出一个数x使得有且仅有k个数字小于x

有幸100%

import sys
if __name__ == "__main__" :
    # n组数据
    n_data = int(sys.stdin.readline())
    for _ in range(n_data):
        
                # 获取n,k
        n_k = sys.stdin.readline()
        nk = list(map(int,n_k.split()))
        n , k = nk[0] , nk[1]

        # 获取n个数
        line = sys.stdin.readline()
        L = list(map(int,line.split()))

        # 对数据进行重排列
        L.sort()

        # 看是否能在k处插入值
        # 观察k是否越界
        if k > n or k < 0: print("False")

        # 观察k是否到尽头
        elif k == n : 
            if L[n-1] < n :
                print("True",'
',L[n-1]+1)
            else:
                print("False")

        # 观察k是否在开头
        elif k == 0 :
            print("True",'
',1)

        # 若k在中间
        elif L[k-1] < L[k] : 
            print("True",'
',L[k-1]+1)
        else :
            print("False")

2、奇怪的键盘，去除输入数组中的空格和相邻重复字母

有幸100%通过，也就这两题了，后面一道比一道凉😭😭

import sys
if __name__ == "__main__" :
    line = sys.stdin.readline().strip()
    L = line.split()

    # 去掉空格后重新排布成字符串
    tran = ''.join(L)

    # 初始化存放答案的数组和上一个碰到的字符，"#"表示空
    ans , last = [] , '#'

    # 遍历重排后的字符串，若和上一个碰到的相同，则跳过，不同则加入到答案
    for ch in tran:
        if ch == last : continue
        else : 
            ans.append(ch)
            last = ch
    print(''.join(ans))

3、输入一个数组，设p[i]为数组第i个数字A[i]前最大且小于A[i]的数，若不存在，则p[i]为0，求 $\sum{p[i]\cdot i}$

这个题目的通过了只有62%，我相信写得没错，猜测是因为有些数组太长导致超时了，虽然我只用一个循环，但可能重排列表太多次导致超时了？？？🤔🤔

import sys
if __name__ == "__main__" :
    n = int(sys.stdin.readline())
    line = sys.stdin.readline()
    nums = list( map(int,line.split()) )
    
    # 用一个列表存放出现过的数字,初始化输出
    appear , ans = [nums[0]] , 0
    for i in range(1,len(nums)) :
        
        # 如果该数字没出现，则按顺序插入到appear中
        if nums[i] not in appear:
            appear.append(nums[i])
            appear.sort()
        
        # 该数字插入后的前一个数即为符合条件的数
        point = appear.index(nums[i])
        if point > 0 : 
            ans += appear[point-1] * (i+1)
    print(ans)