25年11月9日下午15:00于深圳出租屋内参加26届中国移动数智化部的笔试

一共两个算法题目，第一个是签到题，不难

第二个题目看着挺花哨，但题意是：给一个数组，求所有两两数字之差的绝对值的和

比如

1
2
3
4
5
[4, 2, 0]
# 4 - 2 = 2
# 4 - 0 = 4
# 2 - 0 = 2
res = 2 + 4 + 2 = 8

但有时间限制，不能套双循环求，如果用下面的双循环，只能通过50%（会超时）

1
2
3
for i in range(LenData):
    for j in range(i + 1, LenData):
        countChange += data[j] - data[i]

好玩的是，我添加了下面的代码，防止出现[3,3,3,3,3]这种情况，通过率上升到56%

1
2
3
4
5
6
7
8
if LenData == 1:
        print(0)
        return
    for i in range(1, LenData):
        dataDiff.append(data[i] - data[i - 1])
    if sum(dataDiff) == 0:
        print(0)
        return

本题目关键在于，如何不用双循环快速求解

比如输入: [4, 1, 5, 7, 12]，为了方便后续观察，我将其先排序

得到[1, 4, 5, 7, 12],随后求两个数之差

得到

3 4 6 11
1 3 8
2 7
5

注意，对角线的差值，表示两个相邻元素之差

并且，我们能观察到，1与5的差值，等于1与4的差值加上4与5的差值；1与12的差值等于所有相邻差值相加，于是我们可以得到下表

3 3+1 3+1+2 3+1+2+5
1 1+2 1+2+5
2 2+5
5

于是！

1
3 * 1*(n-0) + 1 * 2*(n-1) + 2 * 3*(n-2) + 5 * 4*(n-3)

我们可以得到个公式，令d_i为每个差值

1
d_i * (i + 1) * (n - i)

其中i为下标，n为差值数组长度

最后，用一次循环即可得到总的差值和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def main():
    n = int(input())
    data = sorted(list(map(int, input().split())))
    dataDiff = list()
    
    LenData = len(data)
    if LenData == 1:
        print(0)
        return
    for i in range(1, LenData):
        dataDiff.append(data[i] - data[i - 1])
    if sum(dataDiff) == 0:
        print(0)
        return
    countChange = 0
 
    LenDataDiff = len(dataDiff)
    for i in range(LenDataDiff):
        countChange += dataDiff[i] * (i + 1) * (LenDataDiff - i)
    
    print(countChange)

if __name__ == "__main__":
    main()