Anonymous : 求数组中元素为另外两个元素和的最大元素

对于正数数组A[n], 找出A[i] = A[x]+A[y]的A[i]的最大值。
时间复杂度O(nlogn), 空间复杂度O(1)

1)对数组排序O(nlgn)后， 二分查找
2)利用快排想法，每次分开两半，然后看那一半比较接近A[x]+A[y]，继续快排那段

1)对数组排序O(nlgn)后， 二分查找
2)利用快排想法，每次分开两半，然后看那一半比较接近A[x]+A[y]，继续快排那段
bill 发表于 2011-5-15 01:15

   .... 你在说虾米，好像不对

回复 1# wwwyhx
有nlogn的做法吗？感觉不用n^2很难出来啊

回复  wwwyhx
有nlogn的做法吗？感觉不用n^2很难出来啊
darksteel 发表于 2011-5-15 08:58

额～～，前端时间你不是说杨氏矩阵吗？？还是你告诉我的咋又忘了列。。。
杨氏矩阵查找一个数用二分法的话是logn哈..... 这题里的杨氏矩阵实际上也不用真的列出来，用到的时候在加就可以了，所以不要求额外空间。就是排序+杨氏矩阵

回复 5# wwwyhx
其实我对那个了解也不多。。。不过怎么感觉用不太上呢，杨氏矩阵内的搜索应该是O(m+n)的啊

回复  wwwyhx
其实我对那个了解也不多。。。不过怎么感觉用不太上呢，杨氏矩阵内的搜索应该是O(m+n)的啊
darksteel 发表于 2011-5-15 11:39

    杨氏的搜索可以用2分啊，做到logm+logn，这里就是logn
    对a[n]里每个元素，从大到小在杨氏矩阵查找是否存在，找到了，和就出来了(Young(i,j)[i] = a[i][i](i) + a[j])[/i][/i][/i]

回复 7# wwwyhx


    如果我没有理解错的话，你的意思是将所有的A[i]+A[j]构造成一个杨氏矩阵，然后再搜索？那构造过程不就平方了么？

回复  wwwyhx


    如果我没有理解错的话，你的意思是将所有的A+A[j]构造成一个杨氏矩阵，然后再搜索？那构造过程不就平方了么？
epic 发表于 2011-5-20 10:54

    不是，你更本就不需要构造，实际上也不用实际占用空间，这个杨氏矩阵的Young[i][j] = a[i]+a[j],不需要构造，不需要额外空间，是个概念上的杨氏矩阵

回复 9# wwwyhx


    理解不能，求伪代码或例子。