在数组O（n）中找到一对相等的整数？

3 回答

• 1

  Counting sort

  如果输入允许您使用计数排序，那么您所要做的就是在O（n）时间内对输入数组进行排序，然后在O（n）时间内查找重复项 . 可以改进此算法（虽然不复杂），因为您实际上不需要对数组进行排序 . 您可以创建计数排序使用的相同辅助数组，它由输入整数索引，然后逐个添加这些整数，直到已插入当前整数 . 此时，已找到两个相等的整数 .

  此解决方案提供最坏情况，平均和最佳情况的线性时间复杂度（ O(n) ），但要求输入整数位于 known and ideally small range 中 .

  Hashing

  如果您不能使用计数排序，那么您可以使用哈希表而不是辅助数组来回退哈希并使用与之前相同的解决方案（无需排序） . 哈希表的问题在于其操作的最坏情况时间复杂度是线性的，而不是常数 . 实际上，由于碰撞和重新划分，插入在最坏的情况下在O（n）时间内完成 .

  由于您需要O（n）插入，这使得该解决方案的最坏情况时间复杂度呈二次方（ O(n²) ），即使其平均和最佳情况时间复杂度是线性的（ O(n) ） .

  Sorting

  如果计数排序不适用，另一种解决方案是使用另一种排序算法 . 基于比较的排序算法的最坏情况时间复杂度最多为O（n log n） . 解决方案是对输入数组进行排序，并在O（n）时间内查找重复项 .

  该解决方案具有最坏情况和平均时间复杂度 O(n log n) ，并且取决于排序算法，最佳情况线性时间复杂度（ O(n) ） .

  回复于 2024-04-28T04:50:07+08:00
• 2

  以下是Counting Sort的伪代码：

  #    input -- the array of items to be sorted; key(x) returns the key for item x
  #    n -- the length of the input
  #    k -- a number such that all keys are in the range 0..k-1
  #    count -- an array of numbers, with indexes 0..k-1, initially all zero
  #    output -- an array of items, with indexes 0..n-1
  #    x -- an individual input item, used within the algorithm
  #    total, oldCount, i -- numbers used within the algorithm
  
  # calculate the histogram of key frequencies:
  for x in input:
      count[key(x)] += 1
  
  # calculate the starting index for each key:
  total = 0
  for i in range(k):   # i = 0, 1, ... k-1
      oldCount = count[i]
      count[i] = total
      total += oldCount
  
  # copy to output array, preserving order of inputs with equal keys:
  for x in input:
      output[count[key(x)]] = x
      count[key(x)] += 1
  
  return output
  

  如您所见，所有键都在0 ... k-1的范围内 . 在您的情况下，数字本身是关键，它必须在一定的范围内，以便计算排序适用 . 只有这样才能在O（n）中用O（k）空间完成 .

  否则，使用任何基于比较的排序，解决方案是O（nlogn） .

  回复于 2024-04-28T04:50:07+08:00
• 3

  如果您订阅整数排序为O（n），那么无论如何这是O（n），通过排序迭代直到两个相邻元素比较相等 .

  在最坏的情况下，散列实际上是O（n2）（你有世界上最差的散列算法，它将所有内容散列到相同的索引） . 虽然在实践中使用哈希表来获取计数会给你线性时间性能（平均情况） .

  实际上，线性时间整数通过将用于表示整数的位数固定为某个常数k来排序“作弊”，然后可以忽略该常数 . （实际上，这些都是很好的假设，整数排序可以非常快！）

  在最坏的情况下，基于比较的排序（如合并排序）将为您提供O（n log n）复杂度 .

  您所说的XOR解决方案是在两个相同的整数列表之间找到一个唯一的“额外”项 .

  回复于 2024-04-28T04:50:07+08:00