java - 验证代码的空间复杂度以消除重复

Question

@SuppressWarnings("unchecked")
public static <T> List<T> eliminateDuplicate(List<T> list) {
    Set<T> set = new HashSet<T>(list);
    return (List<T>) Arrays.asList(set.toArray());
}

想要检查上面简单代码的空间复杂度以消除重复。

1. 存储在集合中 -> O(n)
2. 由于 set.toArray - O(n) 生成的数组中的存储
3. 存储在新创建的列表中 - O(n)

总 O(3n) 与 O(n) 相同。

你能帮我确认一下吗？

Answer 1

基本上，是的。总空间利用率是O(N)最终（去重）列表大小的位置N。

但是Arrays.asList(...)正在创建一个占用O(1)空间的包装器（除了它正在包装的数组之外）。