这是一个家庭作业问题，我已经考虑了很长一段时间，并提出了一些解决方案，但我认为存在更好的解决方案。
确定数组中是否存在仅出现一次的元素 （int） 的最快方法是什么？任何元素都可以出现任意次数。{3， 1， 4， 1， 4， 3} 将返回 false，而 {3， 1， 4， 1， 4， 1} 将返回 true（3 出现一次）。
我们只被允许使用我们已经学到的东西（所有基础知识，递归，哎呀，搜索和排序算法，包括快速排序），所以制作哈希表不是一种选择。
到目前为止，我想出的最好的实用解决方案是使用快速排序然后通过它进行排序（O（nlogn），我想出的最好的非实际解决方案是制作一个所有可能的int值大小的大数组，然后使用它的位置类似于哈希表（但该数组太大而无法实际实现）（ O（n） ）
有没有另一种（实用的）方法可以在O（n）时间内做到这一点？
编辑：刚刚从TA那里得到了一个答案，我听到的建议O（n）解决方案是一个不切实际的解决方案（与我建议的相同或相似），因此他们告诉我们不要使用它。我现在有99%的把握，最好的实际答案（没有哈希表）是O（nlogn）时间。
您可以使用自定义的快速排序来查找不同的值，而无需在之后迭代排序的数组。
当您选择了一个透视值并在数组的相应部分之间移动时，如果该值与该透视表匹配，则丢弃它并在数组的某个部分移动后丢弃透视值，这将在数组最终排序之前删除重复项。
结婚
Sorting [5, 1, 4, 1, 4, 1]
If you choose the pivot as 4, you'd end up with the 2 sub arrays being:
[1, 1, 1] and [5]
如果数据透视从不被丢弃，则它是不同的，如果它被丢弃，则在子列表上执行相同的过程。如果子列表只有 1 个元素，则它是不同的。
通过这种方式，您可以更早地获得不同的值。
编辑：是的，这仍然受O（nlogn）的限制（我想？
您基本上必须进行气泡排序样式比较。没有内置的函数来回答这个问题，即使你排序，你仍然必须迭代每个元素（即使只是为了找到组何时中断）。您可以对多个数组执行一些更复杂的方法，尤其是在需要查找哪些元素仅返回一次时。
但是一旦你找到一个出现一次的，你就可以打破。此代码可以做到这一点。它是O（n^2），但我不确定你能更快地解决这个问题。
boolean anySingles(int[] data])
{
outer:
for (int i = 0; i < data.length - 1; i++)
{
for (int j = 0; i < data.length; j++)
{
if (i != j)
{
if (data[i] == data[j]) continue outer;
}
}
// made it to the end without finding a duplicate
return true;
}
return false;
}
