面试题：一个存有10000个数的list对list中的每一个数+1.如何实现

Question

我当时回答的是使用java8的stream类中的map函数+1.
但是看面试官的反应让我确信这不是正确答案。各位会怎么做

Answer 1

Java8 的 Stream 可以并发执行，但 Stream 不会改变原有的 list，只能返回一个新的 list，然后赋值给原来 list 的引用。但是如果 list 是 RandomAccess 的，即底层实现为数组，比如 ArrayList，那么直接使用传统的 for 循环遍历一遍就好，因为对于 RandomAccess 的 List，通过下标访问数组元素的时间复杂度为 O(1)，那么遍历一遍的时间复杂度为 O(N)，这是一个很优的时间复杂度，而且没有使用额外的空间，空间复杂度为 O(1)；
如果不是，比如 LinkedList，那么通过下标获得 list 中对应元素的时间复杂度是 O(N)，如果使用之前的方式，那么总的时间复杂度会是 O(N^2)，那么推荐创建一个同样大小新的 List，然后遍历原有的 list，把 每个元素+1 的值加入到新的 List 中。这个时候时间复杂度是 O(N)，空间复杂度也是 O(N)。（当然此时你也可以使用 Stream 来生成一个新的 List）

---

所以我猜测面试官对你的回答不满意，是因为你没有考虑到不同的 List 类型吧。