java是编写这个程序的最佳方式

Question

我有一个一般的编程问题，我碰巧用Java来回答。问题是：

给定一个整数数组，编写一个程序，找出数组中有多少个非唯一的数字。（例如，{2,3,2,5,6,1,3}2中的数字（2和3）不是唯一的）。你的程序执行多少操作（以O表示法）

这是我的解决方案

int counter = 0;


for(int i=0;i<theArray.length-1;i++){
for(int j=i+1;j<theArray.length;j++){
    if(theArray[i]==theArray[j]){
        counter++;
                    break; //go to next i since we know it isn't unique we dont need to keep comparing it.
            }
}
}

return counter:

现在，在我的代码中，每个元素都会与其他元素进行比较，所以大约有n（n-1）/2个操作。给出O（n^2）。如果您认为我的代码不正确/效率低下，或者我的O表达式错误，请告诉我

Answer 1

你的分析是正确的，但你可以很容易地把它归结为O（n）时间。在遍历数组时，尝试使用HashMap<Integer,Integer>存储以前看到的值（key是您看到的数字，value是您看到它的次数）。每次尝试向hashmap中添加一个整数时，请检查它是否已经存在。如果是，只需增加整数计数器。然后，在最后，在地图中循环，并计算您看到相应值大于1的键的次数

Answer 2

正如其他人所说，O（n）解决方案很可能使用散列。在Perl中：

my @data = (2,3,2,5,6,1,3);
my %count;
$count{$_}++ for @data;
my $n = grep $_ > 1, values %count;
print "$n numbers are not unique\n";

输出

2 numbers are not unique

Answer 3

我认为你的O(n^2)时间复杂度是正确的

如果空间复杂度不是问题，那么可以使用256个字符（ASCII）的标准数组，并开始用值填充它。例如 //可能需要将所有值初始化为0。我不知道。但是下面可以用O(n+m)完成，其中n是数组的长度，m是数组的长度

int[] array = new int[256];

for(int i = 0 ; i < theArray.length(); i++)

  array[theArray[i]] = array[theArray[i]] + 1;

for(int i = 0 ; i < array.length(); i++)

  if(array[i] > 1)

        System.out.print(i);

Answer 4

你的代码不符合你的要求。如果使用数组{2, 2, 2, 2}运行它，会发现它返回2而不是1。你必须找到一种方法来确保计数不再重复

然而，作为最坏情况分析，你的大O表达式是正确的，因为每个元素都可能与其他元素进行比较

Answer 5

为什么不像下面的例子那样使用Map

// NOTE! I assume that elements of theArray are Integers, not primitives like ints
// You'll nee to cast things to Integers if they are ints to put them in a Map as
// Maps can't take primitives as keys or values
Map<Integer, Integer> elementCount = new HashMap<Integer, Integer>();
for (int i = 0; i < theArray.length; i++) {
   if (elementCount.containsKey(theArray[i]) {
     elementCount.put(theArray[i], new Integer(elementCount.get(theArray[i]) + 1));
   } else {
     elementCount.put(theArray[i], new Integer(1));
   }
}

List<Integer> moreThanOne = new ArrayList<Integer>();
for (Integer key : elementCount.keySet()) { // method may be getKeySet(), can't remember
   if (elementCount.get(key) > 1) {
      moreThanOne.add(key);
   }
}

// do whatever you want with the moreThanOne list

注意，这个方法需要迭代列表两次（我相信有一种方法可以迭代一次）。它在theArray中迭代一次，然后在迭代elementCount的键集时隐式地再次迭代，如果没有两个元素是相同的，那么键集将完全一样大。然而，连续两次遍历同一个列表仍然是O（n）而不是O（n^2），因此具有更好的渐近运行时间

Answer 6

首先，你的方法就是我所说的“蛮力”，在最坏的情况下，它确实是O（n^2）。它的实现也不正确，因为重复n次的数字被计数n-1次

撇开这一点不谈，有很多方法可以解决这个问题。第一个（许多答案都建议）是迭代数组，并使用一个映射来跟踪给定元素被看到的次数。假设映射使用哈希表作为底层存储，平均大小写复杂度应该是O（n），因为来自映射的get和insert平均应该是O（1），并且您只需要对列表和映射进行一次迭代。请注意，在最坏的情况下，这仍然是O（n^2），因为不能保证哈希将产生连续时间结果

另一种方法是先对数组进行排序，然后迭代排序后的数组以查找重复项。这种方法完全取决于所选的排序方法，可以是O（n^2）（对于简单冒泡排序）到O（n logn）最坏情况（对于合并排序）到O（n logn）平均情况（尽管可能是快速排序）

这是假设数组中存在任意对象的排序方法所能做的最好的事情。不过，因为您的示例涉及整数，所以使用基数排序可以做得更好，它的最坏情况复杂性为O（dn），其中d基本上是常量（因为32位整数的最大值为9）

最后，如果您知道元素是整数，并且它们的大小不太大，那么可以通过使用size ElementMax数组来改进基于映射的解决方案，这将保证O（n）最坏情况的复杂性，同时需要额外的4*ElementMax字节内存