在数组标量中查找重复项

Question

是否有更好的方法在具有更好的时间和空间复杂性的数组中查找重复项，以下是我尝试过的方法

我相信时间复杂度为O（N），空间复杂度为O（1）

def findDuplicates(nums:Array[Int]):ArrayBuffer[Int] ={

    var buckets =new HashMap[Int,String]()
    var outputArr= new ArrayBuffer[Int]()

    nums.foreach(x=>
      if(buckets.contains(x) && buckets(x) == "Im Cool")
      {
        outputArr +=x
      }
      else
        buckets(x) = "Im Cool"

    )

    outputArr
  }

Answer 1

算法的时间和空间复杂度均为O(N)，其中N = |nums|。

时间

HashMap操作contains，put，get都具有平均O(1)时间复杂度，附加到数组上也具有平均O(1)复杂度。您的算法调用contains和get N次，并且put和数组附加最大N次。这给出O(N)。

空格

buckets的大小随N线性增长。在N两倍大的测试用例中，buckets的大小将是适当的。两倍大。与outputArr相同。因此，这也给出O(N)。

优化

您的方法在理论复杂度方面是最佳的。因为重复的元素可以在输入数组中的任何位置，所以除非您对数组有一定的了解，否则您必须阅读每个元素。因此，时间复杂度不能小于O(N)。

输出数组最多可以包含N-1个元素（例如：[0, 0, 0]返回[0, 0]），因此空间复杂度不能小于O(N)。

但是，通过使用HashSet来存储已经看到的元素，可以在实际速度和可读性方面优化实现。

def findDuplicates(nums:Array[Int]):ArrayBuffer[Int] ={
    var buckets = new HashSet[Int]()
    var outputArr = new ArrayBuffer[Int]()

    nums.foreach(x=>
      if(buckets.contains(x)) {
        outputArr += x
      }
      else {
        buckets.insert(x)
      }

    )

    outputArr
  }

这将删除不可思议的"Im Cool"字符串并保存字符串比较的恒定时间。

Answer 2

def getDuplicates[T](nums: Array[T]): List[T] = {
    nums.foldLeft(Map.empty[T, Int])((a,b) => a.updated(b, a.getOrElse(b, 0) + 1))
      .filter(_._2 > 1).flatMap(e => List.fill(e._2 - 1)(e._1)).toList
  }

时间复杂度：O（N）空间复杂度：仅当不考虑输出数组时，O（N）最坏的情况。如果考虑的空间复杂度将为O（1）。