[算法] 最大的n个元素对
meta
Wu Yin
[问题] 给定两个有序的正整数数组A[n]和B[n], 我们定义如下集合: S = { (a, b} | a in A[n] and b in B[n]}, 很明显S总共有n^2个元素对. 元素对的值定义如下: value(a, b) = a + b.求集合S中值最大的n个元素对.
--
滚滚长江东逝水，浪花淘尽英雄。
是非成败转头空。
青山依旧在，几度夕阳红。
白发渔樵江渚上，惯看秋月春风。
一壶浊酒喜相逢。
古今多少事，都付笑谈中。
----------
Xiamen University Cognitive Science Department, Brain-like Intelligent System Labs
Email: wyw...@gmail.com
Gtalk: wyw...@gmail.com
MSN: wyw...@hotmail.com
meta
Alecs King
one possible way is to use a heap/priority_queue. pseudo^H^H^H^H^Hython
code:
#!/usr/bin/python
#
# for a quick & dirty demo, we just find the n biggest _values_.
# this makes test easy, since the actual pairs might not be unique.
#
# well, you get the idea, feel free to change it to suit your needs.
#
# Beer License -- CopyLeft (D) 1q84 All Wrongs Not Reserved
import heapq
import random
def bestn(A, B):
A.sort(reverse=True)
B.sort(reverse=True)
n = len(A)
score = [(-a - B[0], 0) for a in A]
heapq.heapify(score)
ret = []
for x in xrange(n):
v, k = heapq.heappop(score)
ret.append(-v)
if k < n - 1:
heapq.heappush(score, (v + B[k] - B[k+1], k+1))
return ret
def brute(A, B):
n = len(A)
score = [a + b for a in A for b in B]
score.sort(reverse=True)
return score[:n]
r = random.Random()
n = 1000
limit = 10000
A = [r.randint(1, limit) for x in xrange(n)]
B = [r.randint(1, limit) for x in xrange(n)]
print all(a == b for a,b in zip(bestn(A,B), brute(A,B)))
--
Alecs King
freepro...@gmail.com
最大的肯定是a[n]+b[n]
第二大的是max{ a[n]+b[n-1], a[n-1]+b[n]}
第三大的是min { a[n]+b[n-1], a[n-1]+b[n]}
第四大的则又是 a[n-1]+b[n-1]
以此递推.
Mikster.Z
Wang Feng
> 貌似O(n)就行了。
> 最大的肯定是a[n]+b[n]
> 第二大的是max{ a[n]+b[n-1], a[n-1]+b[n]}
> 第三大的是min { a[n]+b[n-1], a[n-1]+b[n]}
> 第四大的则又是 a[n-1]+b[n-1]
b := {0 0 0 0 }
> 以此递推.
freepro...@gmail.com
不知道有没有算法可以不用算出全部 n^2 个和的。
On Jul 21, 12:44 am, "Mikster.Z" <chinamix...@gmail.com> wrote:
> 你是认为a[n]跟b[n-2]不能是第三大的么....
>
lxcypp
不好意思，发重了
这个问题肯定有O (k )的算法的，
设两个指针从两个数组胃部向前扫描
，最多k 次就应该得到结果
在 2010-7-22 上午1:57，"freepro...@gmail.com" <freepro...@gmail.com>编写：
sigh, 这我都没想清楚
不知道有没有算法可以不用算出全部 n^2 个和的。
> 在 2010年7月21日 下午1:59，freeprogram...@gmail.com <freeprogram...@gmail.com>写道：
On Jul 21, 12:44 am, "Mikster.Z" <chinamix...@gmail.com> wrote:
> 你是认为a[n]跟b[n-2]不能是第三大的么....
>
>
> > 貌似O(n)就行了。
> > 最大的肯定是a[n]+b[n]
> > 第二大的是max{ a[n]+b[n-1], a[n-1]+b[n]}
> > 第三大的是min { a[n]+b[n...
Navi
第一种方法二分第n大的a + b的值记为k，然后对于每个a[i]再在b中二分，计算a[i] + b[j] >= k的个数。时间复杂度O(n*lgn*lg数据范围)
第二种方法是维护数组c[n]全部初始化为n-1，表示a[i]现在匹配到了b[c[i]]。把a[i] + b[c[i]]插入一个堆。每次pop出一个最大的，并把对应的c[i]--，然后把新的a[i] + b[c[i]]插入堆里。一直到pop出n个结果。时间复杂度O(n*lgn)
--
Sincerely.
Navi
meta
Navi
int l = a[0] + b[0], r = a[n - 1] + b[n - 1];
while (l + 1 < r) { /* here is O(lg data range) */
int mid = (l + r) / 2;
int count = 0;
foreach a[i] { /* here is O(nlgn) */
count += the number that a[i] + b[j] >= mid;
}
if (count >= n) {
l = mid;
} else {
r = mid;
}
}
--
Sincerely.
Navi
liuxinyu
设
A的元素为x1, x2, ..., xn
B的元素为y1, y2, ..., yn
下面这个矩阵：
x1 x2 ... xn
y1
y2
... Cij=xi+yj
yn
的特征十分明显：
每一行单调增
每一列单调增
我的算法描述为：
初始：
取上述矩阵的左上角C11放入一个priority queue；
初始化结果序列为空；
循环：
每次从队列中取出头元素Cij放入结果序列中；
检查下述两个候选元素：
C{i+1}j和Ci{j+1}
插入到priority queue中（如有重复则去除）
终止条件，结果序列的长度达到k（原题是n），或priority queue为空。
Python源代码和测试结果如下：
def orderred_insert_by(f, lst, p):
for i in range(len(lst)):
if p == lst[i]:
return
if f(lst[i])>f(p):
lst.insert(i, p)
return
lst.append(p)
def ksum(k, xs, ys):
c=lambda (i, j): xs[i]+ys[j]
res = []
q = [(0, 0)]
while len(res)<k and q!=[]:
(i, j)=q.pop(0)
res.append(c((i, j)))
if i+1<len(xs):
orderred_insert_by(c, q, (i+1, j))
if j+1<len(ys):
orderred_insert_by(c, q, (i, j+1))
return res[:k]
简单的测试代码：
def brute_force(k, xs, ys):
res= [x+y for x in xs for y in ys]
res.sort()
return res[:k]
def test():
for i in range(10):
n= random.randint(1, 1000)
k = random.randint(1, n)
a = random.sample(range(10000), n)
a.sort()
b = random.sample(range(10000), n)
b.sort()
if ksum(k, a, b) != brute_force(k, a, b):
print "fail!"
print "a=", a
print "b=", b
print "k=", k
print "brute-force:", brute_force(k, a, b)
print "ksum:", ksum(k, a, b)
return
print "OK"
if __name__ == "__main__":
test()
运行结果：
# ./ksum.py
OK
Mikster.Z
liuxinyu
难道就非得heapify不可？
On Jul 29, 3:16 pm, "Mikster.Z" <chinamix...@gmail.com> wrote:
> 比朴素的算法还烂
>
yang yang
疯了蓝莓
yang yang
疯了蓝莓
Mikster.Z
liuxinyu
1, A,B已经有序。
2, A, B逐渐取小值相加这个结论不精确。
我举一个有代表性的例子：
A=[5, 100, 200]
B=[1, 2, 3]
还是列成矩阵看着方便:
5 100 200
================
1 | 6 101 201
2 | 7 102 202
3 | 8 103 203
这个矩阵的大小顺序是
1, 4, 7
2, 5, 8
3, 6, 9
也就是a[1]+b[1], a[1]+b[2], a[1]+b[3], ...
而不是通常我们想象的：
小，次小，较大，更大，...
次小，较大，更大,...
较大，更大,...
更大,...
....
On Jul 29, 5:32 pm, yang yang <cyal...@gmail.com> wrote:
> 先排序A,B
> 再从A,B中逐渐取小值相加 保留在a,b
>
> 疯了蓝莓
>
liuxinyu
把矩阵转45度就看清楚了。
c11
c21,c12
c31,c22,c13
..., ..., ..., ...
每次节点展开的宽度为2，然后push回队列。
如果不做重复检测，队列增加的速度为1, 2, 4, ...2^i
总次数为2^(i+1)-1，其中i是弹出元素的次数。
队列不会无限增加，最长达到n^2-n
终止条件是队列弹出k个元素。
以下是一个队列变化的例子：
raw q= [(0, 1), (1, 0)]
raw q= [(1, 0), (1, 1), (0, 2)]
raw q= [(2, 0), (1, 1), (0, 2)]
raw q= [(3, 0), (1, 1), (2, 1), (0, 2)]
raw q= [(1, 1), (2, 1), (3, 1), (0, 2), (4, 0)]
raw q= [(2, 1), (3, 1), (0, 2), (1, 2), (4, 0)]
raw q= [(3, 1), (0, 2), (1, 2), (2, 2), (4, 0)]
raw q= [(0, 2), (1, 2), (2, 2), (3, 2), (4, 0), (4, 1)]
raw q= [(1, 2), (2, 2), (3, 2), (4, 0), (4, 1), (0, 3)]
On Jul 29, 5:36 pm, "Mikster.Z" <chinamix...@gmail.com> wrote:
> 1：线性查找
> 2：重复检测
> 3：你知道你的复杂度是多少么...
>
Mikster.Z
Devymex
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
using namespace std;
struct INDEX { //存储节点的坐标和截距
int nCol; int nRow; int nIntercept;
} idx; //临时变量
//比较节点截距大小的回调函数
bool lessidx(int nIntercept, INDEX dest) {
return (nIntercept > dest.nIntercept);
}
void main(void) { //主函数
int aColNums[] = { 29, 27, 21, 12, 7, 6, 3 }; //示范数据
int aRowNums[] = { 18, 15, 11, 8, 5, 3, 1 };
const int nCols = sizeof(aColNums) / sizeof(aColNums[0]); //数组大小
const int nRows = sizeof(aRowNums) / sizeof(aRowNums[0]);
size_t n = nCols * nRows; //按顺序输出全部的值，可改为较小的值
int aColsTail[nCols] = { 0 }; //各列的末尾指针
list<INDEX> listLine;
idx.nIntercept = aColNums[idx.nCol] + aRowNums[idx.nRow];
listLine.push_back(idx); //将右上角最大的数加入数组，初始化
aColsTail[0] = 1; //第0列末尾指针下移一位
for (; n > 0 && listLine.size() > 0; --n) {
idx = listLine.front(); //将战线中最大的元素输出
listLine.pop_front(); //弹出
cout << aColNums[idx.nCol] << '+' << aRowNums[idx.nRow] <<
'=' << idx.nIntercept << endl;
if (aColsTail[idx.nCol]++ < nRows ) { //如果下面还有
idx.nIntercept = aColNums[idx.nCol] + aRowNums[++idx.nRow];
listLine.insert(find_if(listLine.begin(), listLine.end(),
bind1st(ptr_fun(lessidx), idx.nIntercept)), idx);
} // 如果左边有未动的列
if (++idx.nCol < nCols && aColsTail[idx.nCol] == 0) {
++aColsTail[idx.nCol]; //将这列的第一个元素加入战线
idx.nRow = 0;
idx.nIntercept = aColNums[idx.nCol] + aRowNums[idx.nRow];
listLine.insert(find_if(listLine.begin(), listLine.end(),
bind1st(ptr_fun(lessidx), idx.nIntercept)), idx);
}
}
}
=========签名档=========
待到土共灭亡日，家祭无忘告乃翁！
欢迎 Follow @devymex
Devymex
算法思路
将所有数据按矩阵排列，然后按常规坐标轴的比例进行展部，可以形成如下图形：
每一个红点所代表的数，为纵坐标值和横坐标值相加得到的和。显然，最右上角的数最大。将所有数分为两个部分，一是占领区，二是敌区，在两个区之间构造一条战线，每次攻占战线中最薄弱的一环（最大值），然后顺势将战线推进至下方元素，以此类推。整个战局由最右上角开始向左下角推。
开始先将最大的<7,5>拿下，战线往下推，攻占<7,3>。这时发现左边的一列还没有任何元素被占领。迅速将<6,5>拿下后，此时战线的最薄弱点就是<6,5>
将<6,5>吃掉后战线下推，并发现左边的列3仍没有任何元素被占。将<3,5>纳入战线，此时，最薄弱点是<7,3>
以下过程和上面类似
liuxinyu
http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf
解释下，还是延续前面的矩阵思路，这个矩阵其实组成了一个Young Tableau。
不用一开始把全部的Young Tableau全部生成，需要哪个cell Cij时用a[i]+b[j]计算即可。
算法描述如下：
1. 取Young Tableau的C11元素，作为min
2. 然后Youngify
3. 重复1,2 k次即得前k小的元素。
另：Young Tableau在CLRS的习题
Problems 6-3: Young tableaus
Devymex
一般来讲，如果是从队列头开始线性查找的话，这个算法的复杂度就取决于每一轮队列的长度。队列越短，复杂度越低。按照我上面提供的算法描述，战线的最长长度就等于列数。因此当两个数组长度不等时，让较短的一组作为列会让战线的长度缩短，尤其是两个数组长度差别很大的时候。这在你的算法中也是一样的。
为方便讨论，下面仅考虑行数和列数相同的情况。现假定列数为c，队列用链表存储（插入复杂度为O(1))，最差的情况就是每个新元素入列都会被放到最后，这样整个算法的复杂度就是O(n*c)，最好的情况是每个新元素入列都是头一个，总体复杂度为O(n)。
如果数组长度及其值都是随机的，要想确定地计算出这个算法的平均复杂度非常困难。我尝试着进行分析，但没有成功，过程复杂到超出了我的能力范围。
随后我对大量的随机数进行了实验，发现平均的情况接近于O(n*c)，但还有点距离。离O(n)就比较远了。初步统计了一下，曲线可以近似的用(ln(n) * 3 + 1) * n来拟合。分析原因可能是因为每次新的元素相对于原来的战线都会显得比较“突兀”，明显大于原战线上的值，这样在插入新元素时就会导致更多的查找遍例。
于是我就把查找过程反过来，从队列最后一个元素开始查找，得到了比较好的结果，算法的复杂度已经接近O(n)了。显然这个算法的复杂度不可能低于O(n)，但还有没有可能进一步优化呢？请各位不吝赐教。
liuxinyu
def __init__(self, xs, ys):
self.young = {}
self.c = lambda i, j: xs[i]+ys[j]
self.size = (len(xs), len(ys))
self.infinity = xs[-1]+ys[-1]+1000
def get(self, i, j):
if (i,j) not in self.young:
self.young[(i, j)]=self.c(i, j)
return self.young[(i,j)]
def set(self, i, j, x):
self.young[(i, j)]=x
def swap(self, i1, j1, i2, j2):
x = self.get(i1, j1)
y = self.get(i2, j2)
self.set(i1, j1, y)
self.set(i2, j2, x)
本质上我用一个dict来记录某个Y[i,j]是否已经求出过。
下面的young_pop相当于heap中的extract_min：
def young_pop(young):
x = young.get(0, 0)
young.set(0, 0, young.infinity)
youngify(young, 0, 0)
return x
而类似于heapify的youngify定义如下：
def youngify(young, i, j):
(m, n) = young.size
while True:
(min_i, min_j)=(i, j)
if i+1 < m and young.get(i, j) > young.get(i+1, j):
(min_i, min_j) = (i+1, j)
if j+1 < n and young.get(min_i, min_j) > young.get(i, j+1):
(min_i, min_j) = (i, j+1)
if (min_i, min_j) != (i, j):
young.swap(i, j, min_i, min_j)
(i, j) = (min_i, min_j)
else:
break
求前k小的元素和实现如下：
def ksum(k, xs, ys):
young = lazy_yong_tableau(xs, ys)
res=[]
for i in range(k):
res.append(young_pop(young))
return res
下面是个简单的测试：
res= [x+y for x in xs for y in ys]
res.sort()
return res[:k]
def test():
for i in range(10):
n= random.randint(1, 1000)
k = random.randint(1, n)
a = random.sample(range(10000), n)
a.sort()
b = random.sample(range(10000), n)
b.sort()
if ksum(k, a, b) != brute_force(k, a, b):
print "fail!"
print "a=", a
print "b=", b
print "k=", k
print "brute-force:", brute_force(k, a, b)
print "ksum:", ksum(k, a, b)
return
print "OK"
if __name__ == "__main__":
test()
运行结果：
OK
Yongify的复杂度为O(n)，故而总复杂度为O(k*n)，k为n时退化为O(n^2)。
考虑lazy实现中的dict，实际代价还要更大。这个解仅供娱乐吧。
tom sun
O（K）
liuxinyu
On Aug 3, 10:03 am, tom sun <vince.s....@gmail.com> wrote:
> 这个问题显然可以看成是归并排序最后一步对两个字串的整合。
> O（K）
l w
emuer
自己试了一下，新宇的BFS+priority queue的确能得到正解
On Jul 29, 3:32 pm, Devymex <devy...@gmail.com> wrote:
> 前提：数组已按降序排序，n不超过两数组元素数量之积。
>
> 算法思路
>
> 将所有数据按矩阵排列，然后按常规坐标轴的比例进行展部，可以形成如下图形：
> [image: sum1.PNG]
>
> 每一个红点所代表的数，为纵坐标值和横坐标值相加得到的和。显然，最右上角的数最大。将所有数分为两个部分，一是占领区，二是敌区，在两个区之间构造一条战线， 每次攻占战线中最薄弱的一环（最大值），然后顺势将战线推进至下方元素，以此类推。整个战局由最右上角开始向左下角推。
>
> 开始先将最大的<7,5>拿下，战线往下推，攻占<7,3>。这时发现左边的一列还没有任何元素被占领。迅速将<6,5>拿下后，此时战线的最薄弱点就是<6, 5>
>
> [image: sum2.PNG]
>
> 将<6,5>吃掉后战线下推，并发现左边的列3仍没有任何元素被占。将<3,5>纳入战线，此时，最薄弱点是<7,3>
> [image: sum3.PNG]
> 以下过程和上面类似
> [image: sum4.PNG][image: sum5.PNG][image: sum6.PNG]
> [image: sum7.PNG][image: sum8.PNG][image: sum9.PNG]
>
> =========签名档=========
> 待到土共灭亡日，家祭无忘告乃翁！
> 欢迎 Follow @devymex <https://twitter.com/devymex>
>
> 2010/7/30 Devymex <devy...@gmail.com>
> > 欢迎 Follow @devymex <https://twitter.com/devymex>
>
> > 2010/7/29 Mikster.Z <chinamix...@gmail.com>
>
> > 你是对的~~
> sum3.PNG
> 1KViewDownload
>
> sum4.PNG
> 1KViewDownload
>
> sum2.PNG
> 1KViewDownload
>
> sum7.PNG
> 1KViewDownload
>
> sum8.PNG
> 1KViewDownload
>
> sum6.PNG
> 1KViewDownload
>
> sum5.PNG
> 1KViewDownload
>
> sum1.PNG
> 1KViewDownload
>
> sum9.PNG
> 1KViewDownload