9.27 百度笔试
我是客户端方向的
题目题解如下
题目1：（100%）
给出一个长度为n的数组，统计其中差值为k的数对的数量。
其中，数对的定义是，从数组中选择两个位置不同的数字，即可组成一个数对。
1 <= n, k <= 100000，数组中每个数字的范围在[1, 200000]之间
其中，数对的定义是，从数组中选择两个位置不同的数字，即可组成一个数对。
1 <= n, k <= 100000，数组中每个数字的范围在[1, 200000]之间
思路：
最先的思路是遍历找到差值k存在的个数，计算重复最后整除2，只过了82%（时间超限）
所以改进一下，先统计处所有数的个数，存在数组中，然后根据差值计算结果，全部通过。
参考代码：
if __name__ == "__main__": # n, k = map(int, input().split()) # num = list(map(int, input().split())) # res = 0 # for i in num: # res += num.count(i+k) # res += num.count(i-k) # print(res//2) n, k = map(int, input().split()) num = list(map(int, input().split())) li = [0 for _ in range(max(num) + 5)] res = 0 for i in num: li[i] += 1 for i in range(len(li)): if i + k < len(li): res += li[i] * li[i + k] else: break print(res)
题目2：（100%）
在T城有一条很长的路，路上有n位居民和m家商场，每个居民和商场的位置各不相同，这座城的居民都喜欢节约时间，所以他们只会选择去相距自己最近的一个商场购物，如果有两个商场离一位居民的距离相同，那么他会选择坐标更小的那一个。
现在请你帮助计算一下，每个商场会被多少位居民选择。
（1≤ n ≤50000，1≤ m ≤50000）
现在请你帮助计算一下，每个商场会被多少位居民选择。
（1≤ n ≤50000，1≤ m ≤50000）
思路：
最先就是双层遍历，查找每个人的最近的商场，最后输出结果，只过了73%（时间超限）
所以改进一下，每个人把所有商场都遍历一遍太耗费时间了，所以给商场排个序，找到居民左右的两个商场，比较即可，全部通过
参考代码：
def find(market, people): left = 0 right = len(market) - 1 while left <= right: mid = (left + right) // 2 if market[mid][0] > people: right = mid - 1 else: left = mid + 1 if right < 0: right = 0 if left > len(market) - 1: left = len(market) - 1 return right, left if __name__ == "__main__": # n, m = map(int, input().split()) # zb = list(map(int, input().split())) # li = list(map(int, input().split())) # people = [] # mark = [] # for i in range(len(li)): # if li[i] == 1: # mark.append(zb[i]) # else: # people.append(zb[i]) # res = [0 for _ in range(len(mark))] # for i in range(len(people)): # wz = 0 # for j in range(1, len(mark)): # if abs(mark[j] - people[i]) < abs(mark[wz] - people[i]): # wz = j # res[wz] += 1 # for i in res: # print(i, end=" ") # print() n, m = map(int, input().split()) zb = list(map(int, input().split())) li = list(map(int, input().split())) people = [] market = [] count = 0 for i in range(len(li)): if li[i] == 1: market.append([zb[i], count]) count += 1 else: people.append(zb[i]) res = [0 for _ in range(len(market))] market.sort(key=lambda x: x[0]) for i in range(len(people)): left, right = find(market, people[i]) if abs(market[right][0] - people[i]) < abs(market[left][0] - people[i]): res[market[right][1]] += 1 else: res[market[left][1]] += 1 for i in res: print(i, end=" ") print()
类似资料：