由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - java remove elements in collections时间复杂度 2钟方法一样么
相关主题
灭三哥也不容易问一道题的优化以及时间复杂度
word break 2的时间复杂度是多少 这个解法问一个时间复杂度的问题,求教求教
问一道面试题两个面试题
刚刚结束的linkedIn电面unique binary search II 这题目recursive解法可以么?复杂度是多少?
请教一道面试题请教下3sum为撒超时
Bloomberg 电面how would you create the index for a book
Google onsite归来新鲜Amazon面经(附参考答案) 顺便求各种大公司refer
问道G 的题为什么我写的binary search 比 linear还慢?
相关话题的讨论汇总
话题: iterator话题: predicate话题: method话题: remove话题: 复杂度
进入JobHunting版参与讨论
1 (共1页)
t**r
发帖数: 3428
1
Method 1
items.removeIf(i -> predicate(i));
Method 2
for (Iterator it = items.iterator(); it.hasNext();) {
if (predicate(it.next())) {
it.remove();
}
}
假设是操作一个list. remove其中的m个元素。
问这2个方法时间复杂度是不是一样
s**x
发帖数: 7506
2
这个太基本了,当然都是linear 了,you have to walk through every node. Delete
one node is O(1). 有什么疑问吗?
t**r
发帖数: 3428
3

Delete

【在 s**x 的大作中提到】
: 这个太基本了,当然都是linear 了,you have to walk through every node. Delete
: one node is O(1). 有什么疑问吗?

s**x
发帖数: 7506
4
感情是考人阿?你的反例是arrayList, 实际上就是array, remove if 看来做了小小优
化。


: Delete



【在 t**r 的大作中提到】
:
: Delete

t**r
发帖数: 3428
5
也不算,就是分享一下,大家讨论,学习。
很多看起来无脑的问题,其实不想我们想象的那么简单/直白

【在 s**x 的大作中提到】
: 感情是考人阿?你的反例是arrayList, 实际上就是array, remove if 看来做了小小优
: 化。
:
:
: Delete
:

p*****2
发帖数: 21240
6

都mutate了原有的数据了吧?都不是好习惯。

【在 t**r 的大作中提到】
: Method 1
: items.removeIf(i -> predicate(i));
: Method 2
: for (Iterator it = items.iterator(); it.hasNext();) {
: if (predicate(it.next())) {
: it.remove();
: }
: }
: 假设是操作一个list. remove其中的m个元素。
: 问这2个方法时间复杂度是不是一样

t**r
发帖数: 3428
7
京2老师看来是scala用多了,受不了java

【在 p*****2 的大作中提到】
:
: 都mutate了原有的数据了吧?都不是好习惯。

p*****2
发帖数: 21240
8

缺省的实现貌似是一样的呀
default boolean removeIf(Predicate filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}

【在 t**r 的大作中提到】
: 京2老师看来是scala用多了,受不了java
p*****2
发帖数: 21240
9

感觉可以用filter呀。

【在 t**r 的大作中提到】
: 京2老师看来是scala用多了,受不了java
s**x
发帖数: 7506
10
这个是Java 本身的问题,list 和array 混用,C vector 和list 就分的很清楚。


: 也不算,就是分享一下,大家讨论,学习。

: 很多看起来无脑的问题,其实不想我们想象的那么简单/直白



【在 t**r 的大作中提到】
: 京2老师看来是scala用多了,受不了java
j**********r
发帖数: 3798
11
在Collection.remove不是线性的,用iterator是线性的,removeIf基于后者。
p*****2
发帖数: 21240
12

Method 2不也是基于iterator的吗?

【在 j**********r 的大作中提到】
: 在Collection.remove不是线性的,用iterator是线性的,removeIf基于后者。
j**********r
发帖数: 3798
13
是,但是remove不是。remove相当于从数组里拿掉一个,剩下的要前挪。

【在 p*****2 的大作中提到】
:
: Method 2不也是基于iterator的吗?

p*****2
发帖数: 21240
14

看到了。arraylist把default override了。

【在 j**********r 的大作中提到】
: 是,但是remove不是。remove相当于从数组里拿掉一个,剩下的要前挪。
1 (共1页)
进入JobHunting版参与讨论
相关主题
为什么我写的binary search 比 linear还慢?请教一道面试题
问几道题目Bloomberg 电面
G电面题 + 求祝福Google onsite归来
亚麻电面!问道G 的题
灭三哥也不容易问一道题的优化以及时间复杂度
word break 2的时间复杂度是多少 这个解法问一个时间复杂度的问题,求教求教
问一道面试题两个面试题
刚刚结束的linkedIn电面unique binary search II 这题目recursive解法可以么?复杂度是多少?
相关话题的讨论汇总
话题: iterator话题: predicate话题: method话题: remove话题: 复杂度