请教一道Google intern的面试题
给定一个正整数集合 s = {a1, a2, ..., an},
存在ai * aj = ak, i != j != k
试找出满足上述条件的最大数ak，如果不存在满足上述条件的三个数，则输出-1

[解决办法]
O(N^2)

先从小到大排序

for(i=0;i <n;i++)
{
for(j=0,k=i;j <=i && k <n;)
{
if(a[i]*a[j]==a[k])return; //find
else if(a[i]*a[j]> k)k++;
else j++;
}
}

return -1;
[解决办法]
先按递增排序，复杂度o(nlogn)

计算在已排好序的数组中的首元a[0]的平方，即a[0]*a[0]。用二分查找，找到在已排好序的数组中不小于a[0]*a[0]的最低位置big_pos，若big_pos==len，说明无解。

否则：
对区间[big_pos,len)的元素(len是数组的长度),从尾开始向前扫描。

对元素ak，计算它的取整平方根sak=int(sqrt(ak))，用二分查找，找到在已排好序的数组中大于sak的最低位置pos。

对已排好序的数组中区间[0，pos)内的元素ai，检查ak/ai是否为正整数，
a): 若不是，++i；
b): 若是，用二分查找确定区间[pos，k)是否存在值为ak/ai的数，若存在，结束；否则，++i。



[解决办法]
medie2005(阿诺)的方法的复杂度能证明是O(NlogN)的么？

我觉得最坏的情况下的复杂度是O(N＾２);
考虑{2,4,16,256,....,2^(2*（N－１）))的数组；

计算在已排好序的数组中的首元a[0]的平方，即a[0]*a[0]。用二分查找，找到在已排好序的数组中不小于a[0]*a[0]的最低位置big_pos，若big_pos==len，说明无解。
// big_pos=1;

否则：
对区间[big_pos,len)的元素(len是数组的长度),从尾开始向前扫描。

对元素ak，计算它的取整平方根sak=int(sqrt(ak))，用二分查找，找到在已排好序的数组中大于sak的最低位置pos。
//pos=k-1;

对已排好序的数组中区间[0，pos)内的元素ai，检查ak/ai是否为正整数，
a): 若不是，++i；
b): 若是，用二分查找确定区间[pos，k)是否存在值为ak/ai的数，若存在，结束；否则，++i。
//区间[0，pos)内的元素ai，ak/ai都是整数，且在[pos，k)不存在值为ak/ai的数；
//所以必须搜索所有的[0，pos)范围内所有的数；

总的代价应该是O(N^2);



[解决办法]
假设有数组A[1...n]
（1）首先从小到大排序；
（2）假设ai <=aj <=ak
从末尾最大的元素开始，最左边ai从A[1]开始向右搜索，最右边aj从A[i]/A[1]向左搜索
找到的第一个满足条件的ak就是该题的解

算法伪码描述如下：
n = Length[A];
for i=n to 1 step -1
leftBound = 1;
rightBound = A[i]/A[1]; //确定搜索的右边界
while ( leftBound <rightBound )
temp = A[leftBound]*A[rightBound];
if ( temp < A[i] )
then leftBound++;
else if( temp == A[i] )
then return A[i]; //返回，找到该最大的值
else
rightBound -- ;
return -1; //没找到

在最坏的情况下，时间复杂度是O(nlogn+ n2 ）
[解决办法]
1. 不排序，先利用找最大算法找出第一大的值Max
2. 然后利用Max的平方根r作为划分标准将集合s划分为两部分A、B。使得A中小于r，B中大于r
3. 令|A|=a, |B|=b
4. if a> b
5. then 按照从小到大顺序排序B中元素
6. 对A中每个元素x利用二分检索检查在B中是否有元素y使得x*y=s
7. else 按照从小到大顺序排序A中元素
8. 对B中每个元素y利用二分检索检查在A中是否有元素x得x*y=s
9. 不满足的话跳回步骤1找第二大值赋给Max直到所有数都选择后输出-1

屈婉玲老师在我们的课上好像就是说的这个题目

[解决办法]
medie2005(阿诺)的算法复杂度：

1）对于ak，设需要测试的ai的个数为p，则对于每个ai，二分查找的个数为k-p。
2）假设输入是均匀分布的，那么平均情况下,p=k^(1/2)，k-p = k - k^(1/2)。
3) k的取值范围是0--N，平均情况下是N/2，故第二点的p为O(N^(1/2)),k-p为O(N)。
4）查找ak次数，平均情况下为N/2
综上，该算法平均时间复杂度是O(N^(3/2)logN)，小于O(N^2).

而在最坏情况下，p可以达到它的最坏复杂度O(N)，并且k-p也保持O(N)[例如，当某种输入分布使p=k/2时]。此时，算法达到其最坏复杂度O(N^2*logN)，大于O(N^2).

可以对这个算法做一些改进以进一步提高速度。例如，对于二分查找方面，可以改用hash查找。预先用hash表存储所有的输入值（不需要对每个ak建立hash表，只要一次性建立即可，因为根据对ai的限定，如果查找出值，则一定是所需要的），并在原先二分查找的地方，使用hash查找。由于建立整个hash表的复杂度是O(N)，并且整个算法只需建立一次。而查找一次hash表的复杂度是O(1)。所以，这个改进可以使算法的平均复杂度达到O(N^(3/2))，最坏复杂度达到O(N^2)。

[解决办法]
to Vitin(卫亭) ( )

因式分解的话复杂度跟元素的大小相关的，如果元素值比N大很多，那总的复杂度会比N^2大
[解决办法]
这是俺的解法,按俺的测试没超过 O(N^2)

bool MyFind(vector <unsigned int> &vec, unsigned int &result)
{
if(vec.size() < 3)
{
result = -1;
return false;
}

std::sort(vec.begin(), vec.end()); //小到大排序

int count = 0;
vector <unsigned int> ::size_type left, right;
const vector <unsigned int> ::size_type MaxRight = vec.size() - 1; //数组最大下标, 最小下标为 0

for(vector <unsigned int> ::size_type mid = vec.size() - 2; mid > 0; mid--)
{
left = mid - 1;
right = MaxRight;

while(left > = 0 && right > mid)
{
count++;
if(vec[right] == vec[mid] * vec[left])
{
result = vec[right];
cout < <count < <endl;
cout < <vec[right] < < "= " < <vec[mid] < < "* " < <vec[left] < <endl;
return true;
}

if(vec[right] > vec[left])
{
--right;
}
else
{
--left;
}
}
}

cout < <count < <endl;
return true;
}
[解决办法]
先递增排序：a1,a2,...an
因为是递增，假定i <j <k

pseudocode:

for（k=n →1）
for(j = k-1 →1)
{
if(a[k]%a[j] != 0)
countinu;
else
binarysearch(//二分查找[1-j)之间是否存在a[k]/a[j]);

if(存在)
return a[k]; //满足条件的最大数
}

return -1；