在一个数组中查找一个数字及其平方的算法

Question

在一个数组中查找一个数字及其平方的算法

arraysalgorithm

15

我有一个整数数组，需要使用O(n)算法来查找数组中是否包含一个数及其平方，只需要一个对即可。

我尝试过自己解决，但只能找到一个O(n²)的解法。

我考虑使用计数排序，但是内存使用太大。

- gillyb

2

你能使用额外的空间吗？试着想想如何可能使用它。 - Konrad Rudolph

1

发布你已经尝试过的内容会很好。这样我们可以看到你离解决方案有多近。 - Michael Myers

1

数组是否已排序？如果是，我可以想出一个简单的答案。 - Dietrich Epp

问题没有明确限制空间，但我认为它应该是合理的。 - gillyb

请确保您重新登录此处并告诉我们答案是什么！ - Chris H

我建议我们将这个帖子中的“math”标签删除。 - Aryabhatta

12个回答

4

有两种基本的方法可以做到这一点。

对数组进行排序，然后对每个数字的平方执行二分搜索。总体复杂度为O(nlogn)，但需要排序，会破坏原始顺序（这可能对你的情况很重要）。
将数组的所有项插入哈希表中（或任何快速的“set”数据结构）。然后再次迭代数组元素，检查其平方是否存在于哈希表中。使用哈希表可获得O(n)的总体复杂度，但需要额外的O(n)空间。您还可以使用基于树的“set”（例如C++中的“std::set”或Java中的“TreeSet”），这将为您提供O(nlogn)的复杂度。

- MAK

3

如果我们可以假设输入可以通过基数排序在O（N）时间内进行排序，那么我会对Chris的解决方案进行改进：

基数排序输入。
对于结果的第一个元素，线性向前搜索，直到找到它的平方（在这种情况下停止并返回true），或者找到末尾（在这种情况下停止并返回false），或者找到一个大于平方值的值（在这种情况下继续搜索已排序数组的第二个及其后续元素的平方值）。

每个“指针”都是严格向前移动的，因此总体复杂度为O（N），假设基数排序为O（N），平方和比较为O（1）。我想提问者打算让人们做出这些假设。

回应另一篇答案中提问者的评论：如果输入中的整数没有界限，则我认为无法完成。仅计算一个整数的平方就需要大于线性的时间（至少：没有已知的乘法线性算法），所以考虑一个大小为n位的输入，由大小分别为n / 3位和2 * n / 3位的两个整数组成。测试一个是否是另一个的平方不能在O（n）时间内完成。我想。我可能错了。

- Steve Jessop

我给这篇帖子打了一个-1，因为它混淆了“输入”大小的“正常”定义。在“标准”的RAM计算模型中，假定整数足够小（或寄存器足够大）以适合于O(1)寄存器，并且MUL/DIV等操作是O(1)。 - Aryabhatta

我认为我已经说明了为了给出O（N）解决方案而做出的假设。我补充说，教授可能打算让他们做出这些假设。除此之外，您是否还有其他需要添加的内容，以使其不会引起混淆？ - Steve Jessop

在评估算法的时间复杂度时，我们将乘法（等等）视为单个操作。然后通过完成操作所需的次数来评估算法（更准确地说，是随着输入规模增长，操作次数如何增长）。 - BlueRaja - Danny Pflughoeft

有时我们这样做，有时我们将复杂度计算为图灵机（或其他抽象机器）执行的操作次数。这取决于我们是否需要处理任意整数输入，有时需要，有时不需要。这就是我为什么说两种情况都会发生的原因。 - Steve Jessop

我已经去掉了-1。我重新阅读了你的答案。抱歉，可能是我的阅读理解有些混淆。 - Aryabhatta

显示剩余8条评论

1

如果我们使用C/C++ 32位无符号整数，可以存储的最大值为：4294967295 =（2<<32）-1。我们可以存储其平方的最大数字是（1<<16）-1=65535。现在，如果创建一个位数组并将我们是否已经看到该数字及/或其平方存储在数组中（每个“插槽”2位），我们可以将总存储量降至65535/4 = 16384字节。

我认为这不是过度的内存消耗，因此我们应该能够在没有基数排序的情况下完成此操作。 O（N）算法可能如下所示：

uint32_t index(uint32_t i ) { return i/4; }
unsigned char bit1( uint32_t i ) { return 1<<( (i%4)*2 ); }
unsigned char bit2( uint32_t i ) { return 1<<( (i%4)*2 +1 ); }


bool hasValueAndSquare( std::vector<uint32_t> & v )
{
   const uint32_t max_square=65535;

   unsigned char found[(max_square+1)/4]={0};
   for(unsigned int i=0; i<v.size(); ++i)
   {
      if (v[i]<=max_square)
      {
          found[ index(v[i]) ] |= bit1(v[i]);
          if ((found[ index(v[i])] & bit2(v[i])) == bit2(v[i])) return true;
      }
      uint32_t w = (uint32_t)round(sqrt(v[i]));
      if( w*w == v[i] )
      {
          found[ index(w) ] |= bit2(w);
          if ((found[index(w)] & bit1(w)) == bit1(w)) return true;
      }
    }
    return false;
 }

这段代码并没有经过测试，优化也不是很充分，一个合适的整数平方根函数会更好一些。不过编译器应该会内联所有位访问函数，所以它们应该没问题。

需要注意的是，如果我们使用 64 位整数，那么内存消耗将变得更大，我们需要一个 1Gb 的数组而不是一个 16Kb 的数组 - 这可能不太实用。

- Michael Anderson

1

虽然我无法对上面的建议进行补充，但您可以通过首先在数据集中查找最小值和最大值（都是O(n)）并将搜索范围限制在该范围内来减少平均运行时间。例如，如果最大值为620，则我知道列表中没有25或更高的整数具有平方。

- Grembo

1

你可能需要使用两个哈希集合来协助完成。

在迭代时，如果该值已经在“squares”哈希集合中，那么你就找到了一对（该值是前面某个值的平方）；如果该值的平方已经在“values”哈希集合中，那么你也找到了一对（该值的平方已经被检查过）；否则，把该值存储在其中一个集合中，把它的平方存储在另一个集合中。

- NG.

1

个人认为Anon的答案（带有“方块”的小算法）比它看起来更有用：从中删除“从方块中删除所有小于e的”行，该算法可以处理未排序的输入数组。

如果我们假设具有足够空间的典型作业机器，则“方块”数据结构可以建模为布尔标志数组，产生真正的O（1）查找时间。

- Lars

1

不排序，可以处理重复项：

迭代数组以找到最小和最大的整数。 O(n)
创建一个大小为差异的位数组。 O(1) 时间，O(k) 空间
（现在，最小值和最大值之间的每个可能的整数都在数组中有一个对应的位）
迭代旧数组，将找到的每个整数对应的位设置为 1。 O(n)
再次迭代旧数组，检查整数的平方是否具有其对应的位集。 O(n)

（虽然我没有排序，但这个算法可以非常容易地修改为创建一种排序算法，它以 O(n+k) 时间和 O(k) 空间进行排序）

- BlueRaja - Danny Pflughoeft

当然，在现实生活中，这是O(n+k)，因为您需要将整个数组清零；但是我们通常在定义算法时不考虑这些因素。这很可能是“正确”的答案。 - BlueRaja - Danny Pflughoeft

我们通常不考虑那样的事情。其中有些人会考虑，有些人则不会。例如，在查看ISPRIME算法的复杂度时，O(n + k)将是一场灾难，因为k约为2^n。这完全取决于上下文，而我从未在大学里学过计算机科学，无法猜测讲座中可能会提到哪些假设，但在这个SO问题中没有提到... - Steve Jessop

@Steve：我指的是考虑到像将数组清零需要多长时间这样的因素。当然，在大多数其他情况下，k也是一个重要因素。但是，从算法的角度来看，一个数组可以在O(1)中被“声明”为已清零，因此在这种情况下，k不被计算为复杂性的一部分（一个现实世界的例子：理论上，一个数组可以通过硬件中的简单开关在O(1)中被清零；我不知道有哪些计算机实际上实现了这个功能）。 - BlueRaja - Danny Pflughoeft

是的，这是一个很好的观点，因为抽象机器定义将存储视为具有0个初始值（或者至少是一个已定义的初始值，在这种情况下，您将使用它来表示“false”），而malloc提供非确定性值。在实践中，从算法的角度来看，malloc和calloc的时间成本都是不确定的，要分析实际机器上的真实性能，您需要更多的信息... - Steve Jessop

1

优化笔记

哈希集和基数排序算法都可以通过注意以下三个事实进行优化：

奇偶值可以分别处理
计算整数平方根是一种非常快速的操作（通常包括3-5次除法和几次加法）
缓存局部性对这两种算法都很重要

下面的优化算法通常比未优化的情况快5倍，并且使用的RAM不到一半。在某些情况下，如果数据大小与L2/L3缓存大小相似，则它们可能会快100倍或更多。

基于基数排序的优化算法

数据结构是五个整数列表：IN、Aodd、Bodd、Aeven、Beven A和B列表使用IN的一半整数大小。（例如，如果IN = 64位，则A和B = 32位）

扫描列表IN以找到最大的奇数和偶数MAXodd和MAXeven
令LIMITodd = floor(sqrt(MAXodd))
令LIMITeven = floor(sqrt(MAXeven))
对于列表IN中的每个数字：a. 如果是正数，则计算平方根。如果是精确的，则将平方根添加到列表Aodd/Aeven中。b. 如果数字大于等于0且小于等于LIMITodd/LIMITeven，则将其添加到列表Bodd/Beven中。
使用log2(LIMITodd)位对列表Aodd和Bodd进行基数排序
线性扫描Aodd和Bodd以查找匹配项
使用log2(LIMITeven)位对列表Aeven和Beven进行基数排序
线性扫描Aeven和Beven以查找匹配项

如果任何一个线性扫描找到匹配项，则立即返回该匹配项。

这比直接使用基数排序算法快得多的原因是：

被排序的数组通常只有原始值的1/4，每个整数只需要一半的位数，因此在给定排序中使用的RAM总量少于1/8，这对缓存很有好处。
基数排序所用的位数要少得多，导致需要的步骤更少，因此即使它超过了L1或L2缓存，你也会读取更少的RAM，并且读取的RAM也更少。
线性扫描通常更快，因为A列表仅包含精确平方根，而B列表仅包含小值。

基于哈希集的优化算法

数据结构是整数IN的列表，加上两个哈希集A和B。A和B集合使用IN的一半整数大小。

扫描列表 IN，找到最大的奇数和偶数 MAXodd 和 MAXeven
令 LIMITodd = floor(sqrt(MAXodd))
令 LIMITeven = floor(sqrt(MAXeven))
对于列表 IN 中的每个奇数：a. 如果为正，则计算其平方根。如果精确匹配，则检查是否存在于 B 中，如果是则返回，否则将其添加到 A 中。b. 如果该数字大于等于 0 并且小于等于 LIMITodd / LIMITeven，则检查是否存在于 A 中，如果是则返回，否则将其添加到 B。
清除 A 和 B，并针对偶数重复步骤 4。

这比直接使用哈希集算法更快的原因是：

哈希集通常占用 RAM 的 1/8，从而实现更好的缓存性能
仅确切的平方数和小的数字具有哈希集条目，因此花费在散列和添加/删除值上的时间要少得多

此处还有一个额外的小优化：A 和 B 可以是一个单独的哈希集，其中每个条目都带有位标志，表示整数是否在 A 或 B 中（因为它既不能在 A 中又不能在 B 中，否则算法将终止）。

- Ray Burns

0

如果我正确理解问题，您需要检查指定的数字是否在数组中。而不是找到所有在数组中其平方也在数组中的数字。只需维护两个布尔值（一个用于检查数字是否已被找到，另一个用于平方），迭代数组中的元素并测试每个元素。返回两个布尔值的AND。

伪代码如下：

bool ArrayContainsNumberAndSquare(int number, int[] array):
boolean numberFound, squareFound;
int square = number * number;
foreach int i in array
(
  numberFound = numberFound || i == number;
  squareFound = squareFound || i == square;
)
return numberFound && squareFound;

- Sylvestre Equy

1

不，就我所理解的，OP正在寻找在数组中出现的任何一对数字/平方数。 - Kena

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Chris H · Accepted Answer

12

创建一个长度是输入数组两倍的新数组。时间复杂度为O(2N)
在O(N)的时间内复制所有数字
在O(N)的时间内复制数字的平方
进行基数排序(因为都是整数)。时间复杂度为O(N)
遍历一次以查看是否有两个相邻的数字相同。时间复杂度为O(N)
完成！时间复杂度为O(1)

- Chris H

5

如果原始数组中有重复项，会怎样？ - MAK

1

+1：好观点。我没有想到过。不过在O(N)中跟踪仍然相当容易。 - Chris H

3

如果数组中的整数没有边界限制，你该如何进行基数排序？ - gillyb

4

按照相同的论证，如果SIZE_MAX（或等价物）提供了问题规模的有限上限，则快速排序在这类系统上是O(1)。如果您的输入具有大量重复项，则基数排序的O(N)特性非常有趣，但除此之外就不太有用了。 - Steve Jessop

1

如果数组中的整数没有受到限制，那么我相信这是不可能完成的。仅计算一个整数的平方就需要超过线性时间，因此考虑一个由两个相等大小的整数组成的输入。测试一个整数是否为另一个整数的平方不能在O(n)内完成。我想是这样的。 - Steve Jessop

显示剩余7条评论