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

创建一个新数组,长度是输入数组的两倍。O(2n)
复制o(n)中的所有数字
复制0(n)中数字的平方
基数排序(我们可以,因为它们都是整数)o(n)
重复一次以查看是否有两个数字相同,一个接一个o(n)
利润!O(1)

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

1. 对数组排序,然后对每个数字的平方执行二进制搜索。总体的复杂性是O(nlogn),但它需要排序,这将破坏原始排序(这可能对您的案例很重要)。

2. 将数组的所有项插入哈希表(或任何快速 set 数据结构)。然后再次迭代数组的元素,检查其平方是否存在于哈希表中。使用哈希表给出了O(n)的总体复杂性,但您将需要O(n)额外的空间。也可以使用基于树的 设置 (例如) std::set 在C++中或 TreeSet 在Java中,这会给你一个O(nLogn)的复杂性。

如果我们允许输入按基数排序,那么我会改进一下Chris的解决方案:

• 对输入进行基数排序。
• 对于结果的第一个元素,线性向前搜索,直到找到其平方(在这种情况下,以真停止),或者找到结尾(在这种情况下,以假停止),或者找到大于平方的值(在这种情况下,继续搜索排序数组的第二个和后续元素的平方)。

两个“指针”中的每一个都在严格向前移动,所以总的复杂性是O(n),假设基数排序是O(n),平方和比较是O(1)。想必是谁提出了这个问题,就打算作出这些假设。

在回答提问者对另一个答案的评论时:如果输入中的整数不是有界的,那么我认为这是不可能的。仅仅计算一个整数的平方需要大于线性时间(至少:不知道乘法的线性算法),所以考虑一个大小为n位的输入,由两个大小为的整数组成。 n / 3 比特和 2 * n / 3 位。测试一个是否是另一个的平方不能在o(n)中完成。我想。我可能错了。

虽然我不能添加到上面的建议中,但是您可以通过首先找到数据集中的最小值和最大值(O(N))并将搜索限制到该范围来减少平均运行时间。例如,如果最大值是620,我知道列表中没有大于等于25的整数有平方。

你也许可以用一些哈希集来帮助你。

迭代时, 如果该值在squares哈希集中,则会有一对(值是先前找到的值的平方)。 如果平方在值散列集中,则有一对(该值的平方已被传递) 否则,将值存储在一个中,将平方存储在另一个中。

我个人认为,anon的答案(带有‘squares’的小算法)比它看起来更有用:从它的‘squares’行中删除‘remove all less than e from squares’行,该算法可以处理未排序的输入数组。

如果我们假设典型的家庭作业机器有足够的空间,“正方形”数据结构可以被建模为一个布尔标记数组,从而产生真正的O(1)查找时间。

不进行排序,使用重复项:

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

(虽然我没有排序,但是可以很容易地修改该算法以创建 a sorting algorithm 在O(n+k)时间和O(k)空间中是哪一类的)

如果我们使用C/C++ 32位无符号的int,可以存储的最大值是:4294967295=(2和lt;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位整数,那么内存消耗会变得更大,而不是16KB的数组,我们需要一个1GB的数组——可能不太实用。

优化说明

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

1. 奇数和偶数可以分别处理
2. 计算整数平方根是一个非常快速的运算(通常包括3-5除法和几个加法)
3. 缓存位置对于这两种算法都很重要

下面的优化算法通常执行5倍的速度,使用的RAM少于未优化的情况的一半。在某些情况下,如果数据大小与二级/三级缓存大小相似,它们的执行速度可能快100倍或更高。

基于基数排序的优化算法

数据结构是五个整数列表:in、aodd、bodd、aeven、beven A和B列表使用了in的整数大小的一半。(例如,如果in=64位,A&B=32位)

1. 扫描列表以查找最大的奇数和偶数max奇数和max偶数
2. 设limitOdd=楼层(sqrt(maxOdd))
3. 让limiteven=地板(sqrt(maxeven))
4. 对于:a中列表中的每个数字,如果为正数,则计算平方根。如果准确,请将平方根添加到列表aodd/aeven中。b.如果编号为>=0且<=limitOdd/limitEeven,则将其添加到列表BODD/BEVEN中。
5. 仅使用log2(limitodd)位的基数排序列表aodd和bodd
6. 线性扫描AODD和BODD匹配
7. 仅使用log2(limiteven)位的基数排序列表aeven和beven
8. 线性扫描匹配

如果线性扫描发现匹配,则立即返回该匹配。

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

• 排序的数组通常少于值的1/4,并且每个整数只需要一半的位数,所以在给定的排序中使用的RAM总数少于1/8,这对缓存很好。
• 基数排序是在更少的位上进行的,从而减少了传递次数,因此即使它超过了L1或L2缓存,读取RAM的次数也更少,读取RAM的次数也更少。
• 线性扫描通常更快,因为a列表只包含精确的平方根,b列表只包含较小的值。

基于哈希集的优化算法

数据结构是中的整数列表,加上两个哈希集A和B A和B集使用的整数大小是in的一半

1. 扫描列表以查找最大的奇数和偶数max奇数和max偶数
2. 设limitOdd=楼层(sqrt(maxOdd))
3. 让limiteven=地板(sqrt(maxeven))
4. 对于列表中的每个奇数:a。如果为正数,则计算平方根。如果正确,请检查b&return中是否存在平方根;如果为真,请将其添加到a.b中。如果数字为>=0且<=limitOdd/limitEven,请检查a&return中是否存在平方根;如果为真,请将其添加到b中。
5. 清除A和B,对偶数重复步骤4

这比简单的哈希集算法更快的原因是:

• 哈希集通常是RAM数量的1/8,从而获得更好的缓存性能。
• 只有精确的正方形和小数字才有哈希集条目,因此花在哈希和添加/删除值上的时间要少得多。

这里还有一个额外的小优化:a和b可以是一个散列集,它存储每个条目的位标志,以判断整数是在a还是b中(不能同时存在,因为这样算法就会终止)。

如果我正确理解了这个问题,您必须检查数组中是否有指定的数字。也没有找到数组中所有的平方数。 只需维护两个布尔值(一个用于检查是否找到数字,另一个用于平方),迭代数组中的元素并测试每个元素。返回两个布尔值的和。

在伪代码中:

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;

1)使用hashmap可以得到o(n)。

2)如果你使用std::set在2组上:均等和赔率,你可以得到

2*o((n/2)对数(n/2))=o(n log(n/2))

假设平均数大约和赔率一样多

如果数组没有排序,您将无法执行o(n)。

如果对其进行排序,则可以使用该属性在一次传递中进行排序,如下所示:

foreach e in array
    if squares contains e
        return true
    remove all less than e from squares
    add e * e to squares
return false

在哪里? squares 例如,是一个哈希集。

如果不排序,可以在O(n log n)中对其排序,然后使用此方法检查平方,这仍然比足够大的数据集上的原始解决方案更快。