搜索与大O时间限制

Question

对于分配重复，我要创建一个构造函数取一个String [] 名和int [] 排名为完成以下任务O参数（N日志N ）：

（数据验证）：

1. 检查该名称和秩具有相同的长度---（时间：O（1））
个
2. 检查这两个名和排名不是空---（时间：O（1））
3. 将检查不包含任何重复或空字符串名字---（时间：O（n^2））???
4. 检查该秩仅包含不同元件的---（时间：???）

（实际对象declarance）：

• 添加的名称和每个索引值等级到自定义类型的ArrayList（时间：O（n））

对于该项目，我不允许使用数组和ArrayLists之外的任何数据结构（无Map或Set接口），但我可以使用Arrays类中的方法来搜索和排序数组。我没有看到如何在O（n log n）时间完成所有这些事情。我特别不知道如何在小于O（n^2）的时间内完成第3步。谢谢您的帮助！

Answer 1

步骤1 & 2是微不足道的。

第3步：

• 排序与 =>O(n log n)
• 迭代数组检查每个条目与下一个在阵列（看到，如果你发现一个重复的）=>O(n)

==>总共= O (n log n)

步骤4：相同的方法