1

给定一个有序数组，输出所有满足ab=c的三元组，数组示例为：{-24, -15, -8, -6, 0, 3, 6, 9, 17, 36}

4

3 回答 3

3

我将建议O(n^2)基于以下属性的解决方案：如果您修复a并按顺序增加b，则c减少。因此，您可以执行以下操作：

    for( i = 0; i < arr.size(); i++ ) // index of a
    {
        t = arr.size() - 1; // index of possible c
        for( j = 0; j < arr.size(); j++ ) // index of b
        {
            a = arr[ i ];
            b = arr[ j ];
            c = a - b;
            while( t >= 0 && arr[ t ] > c ) // using monotonicity
               t--;
            if( t >= 0 && arr[ t ] == c )
            { /* output a, b, c */ }
        }
    }
于 2013-02-18T18:57:06.727 回答
1

可以O(n^2)通过将所有内容存储a - b在哈希表中然后查询c数组中每个元素的哈希值来完成。

于 2013-02-18T18:32:38.817 回答
0

哈斯克尔版本：

triples set = 
  [[a,b,c] | a <- set, b <- set, b /= a, c <- set, c /= b && c /= a, a - b == c]

*Main> 三元组 [-24, -15, -8, -6, 0, 3, 6, 9, 17, 36]
[[-15,-24,9],[-15,9,-24], [-6,-15,9],[-6,9,-15],[0,-6,6],[0,6,-6],[3,-6,9],[3, 9,-6],[9,-8,17],[9,3,6],[9,6,3],[9,17,-8]]

于 2013-02-19T01:04:27.327 回答