Jun Tarui已经证明，任何使用O(log n)空间的重复项查找器都需要至少Ω(log n / log log n)次通过，这超过了线性时间。也就是说，即使允许对数空间，你的问题也无法解决。
Gopalan和Radhakrishnan有一个有趣的算法，可以在输入上一次遍历和O((log n)^3)空间中找到重复项，这听起来是你最好的选择。
基数排序的时间复杂度为O(kn)，其中k>log_2 n通常被视为一个常数，尽管是一个很大的常数。显然不能在恒定的空间中实现基数排序，但是你可以重用输入数据的空间。
如果您假设数字本身具有某些特征，则可以使用数值技巧。 如果1到n之间的几乎所有数字都存在，则只需将它们相加并减去n（n + 1）/ 2即可。 如果所有数字都是质数，则可以通过忽略除法的运行时间来作弊。
顺便说一下，对于比较排序，有一个众所周知的Ω(log_2(n!))下限，这表明谷歌可能会帮助您找到诸如查找重复项等简单问题的下限。
正如其他人已经提到的，我看不到任何以O(n)的时间复杂度完成它的方法。
然而，您可以尝试使用概率方法，通过使用布隆过滤器。如果你很幸运，它会给你O(n)。
public class DuplicateInOnePass {
public static void duplicate()
{
int [] ar={6,7,8,8,7,9,9,10};
Arrays.sort(ar);
for (int i =0 ; i <ar.length-1; i++)
{
if (ar[i]==ar[i+1])
System.out.println("Uniqie Elements are" +ar[i]);
}
}
public static void main(String[] args) {
duplicate();
}
}