对于作业，我将创建一个构造函数，以 String[] names 和 int[] rank 作为参数，在 O(n log 中完成以下任务n):
(数据验证):
- 检查名称和排名的长度是否相同 ---(时间:O(1))
- 检查名称和排名均不为空 ---(时间:O(1))
- 检查名称不包含任何重复或空字符串 --- (时间:O(n^2))???
- 检查排名是否仅包含不同的元素 ---(时间:???)
(实际对象声明):
- 将names和rank的每个索引值添加到自定义类型的ArrayList中(时间:O(n))
对于该项目，我不允许使用数组和 ArrayList 之外的任何数据结构(没有 Map 或 Set 接口(interface))，但我可以使用 Arrays 类中的方法来搜索和排序数组。我不知道如何在 O(n log n) 时间内完成所有这些事情。我特别不知道如何在不到 O(n^2) 的时间内完成步骤 3。感谢您的帮助!
最佳答案
第 1 步和第 2 步很简单。
第 3 步:
- 使用
Arrays.sort(array)=>O(n log n)对数组进行排序 - 迭代数组，检查每个条目与下一个条目(看看是否找到重复项)=>
O(n)
==> 总计 = O (n log n)
第 4 步:相同的方法
关于java - 搜索具有 Big-O 时间限制的重复项，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22030851/