下面使用 Java 中的 Set 接口(interface)/TreeSet 类实现是否满足 Big-O 表示法中的 O(N*log(N)) 平均时间复杂度。
我试图在提供的整数列表中找到具有上述平均时间复杂度的第 k 个最大元素。
public class JavaBuiltInSort {
public static void removeDupInIntArray(int[] ints, int k) {
Set<Integer> setString = new TreeSet<Integer>(Collections.reverseOrder());
for (int i = 0; i < ints.length; i++) {
setString.add(ints[i]);
}
System.out.println(setString);
Integer[] array = setString.toArray(new Integer[0]);
System.out.println("The kth largest element in the list is "+ array[k-1]);
}
public static void main(String[] args) {
int[] arr = { 8, 9, 4, 5, 2, 1, 6, 5, 7, 9, 5, 4, 8, 6, 3, 1, 2, 5, 4, 7, 8 };
int k = 5;
JavaBuiltInSort.removeDupInIntArray(arr,k);
}
}
最佳答案
来自TreeSet
:
This implementation provides guaranteed log(n) time cost for the basic operations (
add
,remove
andcontains
).
您正在执行 ~log(n) 操作 n 次,因此复杂度确实是 O(n log(n))。
关于java - 在java中使用Set/TreeSet的平均时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20938421/