在数组中总结数字

假设我有一个N个非负整数的数组，每个数都可以非常大（0-> 100,000）。我们还假设N可能非常大（〜100,000,000）。在数组中总结数字

对于数组[a0 a1 ... aN-1]，我想写一个函数，它返回整个数组的（-2）^ ai之和。我想有O（n * log（n））时间复杂度和O（n）空间。

例如，取[1 2 3] - 这将返回（-2）^ 1 +（-2）^ 2 +（-2）^ 3 = -6 另一个限制是对于超过100,000,000 ，函数应该返回-1;

甲幼稚（但错误的）的解决方案是以下内容：

int solve(vector<int> &A) { 
     int answer = 0; 
     for (auto iter = A.begin(); iter != A.end(); ++iter) { 
     answer += pow(-2, *iter); 
     } 
     return (answer <= 1e8) ? answer : -1; 
    }

这不起作用B/C应答会溢出为值> 31（假设天然符号整数大小为4个字节）。对于数组中的值大于63的情况，使用long也不起作用。

我能想到的一个高级解决方案是使用std :: sort对数组进行排序，然后进行排序。对于数组中大于31的值，我们从数组中的值中减去31的倍数。这是可接受的B/C，我们正在处理指数的总和。我很好奇是否有已知的O（n * log（n））复杂度，O（n）空间解决这个问题。

来源

2017-01-23 user1373317

*使用long也不起作用b/c在数组中的值大于63时会失效。* - 如果阻止您实现解决方案的唯一因素是这样，那么有些类允许任意大小的整数，例如[boost :: multiprecision]（http://www.boost.org/doc/libs/1_63_0/libs/multiprecision/doc/html/boost_multiprecision/intro.html）。 – PaulMcKenzie

请注意，(-2)^K具有不同的简单二进制表示形式：它对于偶数K为..00001000..，对于奇数K（2的补码）为..1111110000..。

所以，你可以创建数组（积分或布尔）积累在二进制表示的总和。它的长度应该通过数组中的最大值来确定（开销取决于N - 大约是Log2（N）单元格）。

然后遍历数组，并将当前数字的二进制表示添加到累加器。例如用于阵列A=[2,3,4]

value(K)  binary(-2)^K accum 
          00000000  
2   100   00000100 
3   11111000  11111100 
4   00010000  00001100

每个添加操作花费最大值（A）+ LOG2（N）基本OPS

可能的微型优化 - 排序输入阵列和组重复的值。例如，如果array包含8的值4，则可以轻松地采用8*(-2)^4= 10000 << 3 = 10000000进行单班操作而无需7次添加操作。

来源

2017-01-23 06:37:46 MBo

这是一个很好的解决方案 - 它让我不再看比特表示 – user1373317

一个想法......

你的功能回答2个问题：

1）是否导致适合在100M极限 2）什么是项目超过100M

你再也较低的总和如果1）不满足，则不得不计算后者，所以如果某物适合int或不适合，则最终计数可以不关心。

为了使事情更容易，我们可以使用计数排序和总数。让我们制作计数，它将保持2 ^（i）的乘数，所以最终的总和将是sum（counts [i] * 2^i）。不是计数不使用符号触发器，我们必须在填充它时放置适当的符号。

现在我们可以减少计数阵列。请注意，如果计数[I]> 2，则总和将改性如下数组相同的：

计数[Ⅰ] -2
计数第[i + 1] 1

同样适用于负号。因此，在从0到最大计数的一个循环中，我们可以减少计数值，每个值只剩下0和1/-1。

如您所知，2^N指数的值大于0..2^N-2值中至少2次累加的任何值的总和。因此，如果您的最高指数（减价后）大于28（2^28 = 268,435,456），则结果将不符合100,000,000。

现在，如果1）被占用，你知道最后的和临时的结果不会大于268,435,456，所以它将适合int类型，所以只需要做你的数学并再次检查最终结果。

来源

2017-01-23 09:22:51

在数组中总结数字

回答

相关问题