Python 高性能小算法

[going]

如何高性能计算出一个列表相近 3 个数据的最大值和最小值?

举例：如下列表临近 3 个数据的最大值和最小值 [1,2,3,4,5,7,8,9,10] 输出 最大值为：27 最小值为：6

[hongch]

题目应该指明是无序数组吧？

[hehe12980]

随便给你写了一个
def arr = [1, 2, 3, 4, 5, 7, 8, 9, 10]
if (arr.size() < 3) {
return
}
int min = arr[0] + arr[1] + arr[2]
int max = arr[0] + arr[1] + arr[2]
int prefix = 0
for (int i = 3; i < arr.size(); i++) {
int sum = arr[i] + max - arr[prefix++]
max = Math.max(max, sum)
min = Math.min(max, min)
}
println(min)
println(max)

[hehe12980]

@hehe12980

上面好像写的不太对

def arr = [1, 2, 3, 4, 5, 7, 8, 9, 10]
if (arr.size() < 3) {
return
}
int min = arr[0] + arr[1] + arr[2]
int max = arr[0] + arr[1] + arr[2]
int prefix = 0
for (int i = 3; i < arr.size(); i++) {
int sum = arr[i] + max - arr[prefix++]
max = Math.max(max, sum)
min = Math.min(min, sum)
}
println(min)
println(max)

[ClutchBear]

单纯的 o(n)啊
计算每个元素和后面两个元素的和.
然后比较

[ClutchBear]

data = [1, 2, 3, 4, 5, 7, 8, 9, 10]
max_sum = data[0] + data[1] + data[2]
min_sum = max_sum
temp_list = []
data_length = len(data)

for index, item in enumerate(data):
if data_length == index + 2:
break
temp_list = [item, data[index + 1], data[index + 2]]
temp_list_sum = sum(temp_list)

if temp_list_sum > max_sum:
max_sum = temp_list_sum
if temp_list_sum < min_sum:
min_sum = temp_list_sum
print(max_sum, min_sum)

[BBrother]

数组顺序不能改的话用滑动窗口

[zyb201314]

#这咋样?
import heapq
s=[9,2,3,6,10,5,7,1,8]
print(sum(heapq.nsmallest(3,s)))
print(sum(heapq.nlargest(3,s)))

[Vegetable]

这和遍历一遍找出极值没什么区别吧

[going]

@hongch 是的

[going]

@zyb201314 你这个是排序的结果了，数组是无序的

[todd7zhang]

老老实实遍历就完事，O(n)

[princelai]

高性能用 numpy 啊，你要是刷题没法引入外部包那就没办法了

```
import numpy as np

w=3
arr = np.array([1,2,3,4,5,7,8,9,10])

x,y = np.ogrid[:arr.shape[0]-w+1,:w]
rolling_sum = arr[x+y].sum(axis=1)
# 上两步替代方法
# np.lib.stride_tricks.sliding_window_view(arr,w).sum(axis=1)

print(f"最小值：{rolling_sum.min()}\t 最大值{rolling_sum.max()}")
```

[Pagliacii]

直接遍历不好吗？ https://i.loli.net/2021/03/24/vRDjZtW4ubAL5Qg.png

[livrth]

单调队列 滑动窗口 O （ N ）

[adocder]

应该是考察排序吧