这是一个家庭作业问题，我已经考虑了很长时间，并提出了几个解决方案，但我认为存在更好的解决方案。
确定数组中是否存在仅出现一次的元素（int）的最快方法是什么？任何元素都可以出现任意次数。{3, 1, 4, 1, 4, 3} 将返回 false，而 {3, 1, 4, 1, 4, 1} 将返回 true（3 出现一次）。
我们只能使用我们已经学过的东西（所有基础知识、递归、oop、搜索和排序算法，包括快速排序），因此不能选择制作哈希表。
到目前为止，我想出的最佳实用解决方案是使用快速排序对其进行排序，然后通过它（ O(nlogn) ），我想出的最佳不切实际的解决方案是制作一个大小为所有可能 int 值的大数组，然后使用它类似于哈希表的地方（但该数组太大而无法实际实现）（ O(n) ）
在 O(n) 时间内是否有另一种（实用的）方法可以做到这一点？
编辑：刚从 TA 那里得到答案，我听说的建议 O(n) 解决方案是一个不切实际的解决方案（与我的建议相同或相似），因此他们告诉我们不要使用它。我现在 99% 确定最佳实用答案（没有哈希表）是 O(nlogn) 时间。
您可以使用自定义的快速排序来查找不同的值，而无需在之后迭代已排序的数组。
当您选择了一个枢轴值并在数组的各个部分移动时，如果该值与枢轴匹配，则丢弃它并在您移动通过数组的一部分后丢弃枢轴值，这将在数组之前删除重复项最终被排序。
IE：
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;
}
让我们做一个实验：
package test;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
/**
* Created with IntelliJ IDEA.
* User: Nicholas
* Date: 15.05.13
* Time: 21:16
*/
public class Searcher {
private static boolean searchBySorting(int [] array){
int [] newArray = new int[array.length];
System.arraycopy(array, 0, newArray,0, array.length);
Arrays.sort(newArray);
for (int i = 0; i < newArray.length - 2; ++i){
if(newArray[i] == newArray[i + 1]){
return true;
}
}
return false;
}
private static boolean searchByCompare(int [] array){
int [] newArray = new int[array.length];
System.arraycopy(array, 0, newArray,0, array.length);
for (int i = 0; i < newArray.length - 1; ++i){
int value = newArray[i];
for(int j = i + 1; j < newArray.length - 1; ++j){
if(value == newArray[j]){
return true;
}
}
}
return false;
}
private static boolean searchBySet(int [] array){
int [] newArray = new int[array.length];
System.arraycopy(array, 0, newArray,0, array.length);
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < newArray.length; ++i){
if(set.contains(newArray[i])){
return true;
}
set.add(newArray[i]);
}
return false;
}
private static int [] generateRandomArray(){
Random random = new Random();
int size = random.nextInt(1000) + 100;
int [] array = new int[size];
for (int i = 0; i < size; ++i){
array[i] = random.nextInt();
}
return array;
}
public static void main(String [] args){
long sortingTime = 0;
long compareTime = 0;
long setTime = 0;
for (int i = 0; i < 1000; ++i){
int [] array = generateRandomArray();
long begin = System.currentTimeMillis();
for(int j = 0; j < 100; ++j){
searchBySorting(array);
}
long end = System.currentTimeMillis();
sortingTime += (end - begin);
begin = System.currentTimeMillis();
for(int j = 0; j < 100; ++j){
searchByCompare(array);
}
end = System.currentTimeMillis();
compareTime += (end - begin);
begin = System.currentTimeMillis();
for(int j = 0; j < 100; ++j){
searchBySet(array);
}
end = System.currentTimeMillis();
setTime += (end - begin);
}
System.out.println("Search by sorting: " + sortingTime + " ms");
System.out.println("Search by compare: " + compareTime + " ms");
System.out.println("Search by insert: " + setTime + " ms");
}
}
我的结果：
按排序搜索：2136 毫秒
通过比较搜索：11955 毫秒
按插入搜索：4151 毫秒
有没有问题？
PS。我知道的最好的算法是龟兔赛跑