我有一个List<User> users
,其中User
类有一个属性username
。我还有一个List<User> activeUsers
。设users = activeUsers + inactiveUsers
。现在我想根据username
属性从users
中提取inactiveUsers
。我用两个for循环解决了这个问题。我认为这不是有效的方法。所以,如果有人知道如何有效地做到这一点,请告诉我。
。我有activeUsers[1,3]和users[1,2,3,4],我想建立inactiveUsers[2,4]。
在Java中,您可以使用Collection
接口的removeAll
方法。
// Create a couple ArrayList objects and populate them
// with some delicious fruits.
Collection firstList = new ArrayList() {{
add("user1");
add("user2");
}};
Collection secondList = new ArrayList() {{
add("user1");
add("user1");
add("user3");
add("user4");
}};
// Show the "before" lists
System.out.println("First List: " + firstList);
System.out.println("Second List: " + secondList);
// Remove all elements in firstList from secondList
secondList.removeAll(firstList);
// Show the "after" list
System.out.println("Result: " + secondList);
上面的代码将产生以下输出:
First List: [user1, user2]
Second List: [user1, user2, user3, user4]
Result: [user3, user4]
好吧,根据修改User
类的限制和你的问题的性质,没有办法用两个列表(即两个循环)比o(n^2)
更小。当然,如果每种类型都有两个列表,问题就解决了。
但是既然你不能,那么逻辑是:(假设你的结构只是列表)
Iterate users list (o(n)) :
- Search the active users list for the current user (o(n))
无论你怎么看,你都会得到o(n^2)
如果你可以修改User
有激活属性,你可以很容易地减少o(n)
的问题通过一个单一的搜索
你可以根据用户是否处于活动状态将其存储在Set中,我更喜欢User的属性,但我想你不会希望在你的作业中使用这个。使用此代码,您的问题在O(n)时间内解决。假设你没有弄乱User.
中的equals/hashCodepackage com.stackoverflow.q15999468;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Users
{
public static void main(String[] args)
{
List<User> users = Arrays.asList(u1,u2,u3,u4,u5);
List<User> activeUsers = Arrays.asList(u3,u5);
Set<User> activeUsersSet = new HashSet<User>(activeUsers);
List<User> inactiveUsers = new ArrayList<User>();
for(User user : users)
{
if(!activeUsersSet.contains(user))
{
inactiveUsers.add(user);
}
}
System.out.println("Inactive users: " + inactiveUsers);
}
}
应该可以了
List<User> inactiveUsers = new ArrayList<User>(users);
inactiveUsers.removeAll(activeUsers) ;