12 3 4 5 6 / 6 页下一页

查看: 27025|回复: 51

[问题求助] 两个算法问题

[复制链接]

字体大小: 正常放大

ccf19881030

7 主题	3 听众	154 积分

升级 27%

TA的每日心情

	难过 2012-4-27 07:46

签到天数: 4 天

[LV.2]偶尔看看I

自我介绍: 爱好数学，计算机编程，下象棋

群组: 华中科技大学

电梯直达

1^#

发表于 2010-9-9 19:28 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

1.Google面试题，求kth largest element

you are given 2 arrays sorted in decreasing order of size m and n
respectively.

Input: a number k <= n*m and >= 1

Output: the kth largest sum(a+b) possible. where
a (any element from array 1)
b (any element from array 2)

两个数组A,B 求第k个sum(a+b)。

如果直接一个一个算的话，从大到小，需要O(k)复杂度。
有没有O(logk)或者O(1)的方法。

2.排列与统筹学结合的经典问题

问题：
设方程组（如下）有解：
X1+3+X12=X2
X2+4+X13=X3
X2+4+X14=X4
X3+5+X15=X5
X4+7+X16=X5
X5+8+X17=X6
X6+1+X18=48
X7+5+X19=X8
X8+1+X20=X9
X8+1+X21=X10
X10+2+X22=29
X9+9+X23=X11
X11+7+X24=29
(Xi≥0;i =1,2,…24)

集合:
A={X1,X3,X5,X7,X8,X10,X11};
B={X2,X4,X6,X9};

设A中元素组成m组排列,B中元素组成n组排列.
每个集合中的元素取且仅取一次.(如A中可以形成3组排列:X3X8X7,X1,X5X10X11)
每个排列中元素按照排列顺序满足条件:
Xi+Txi≤Xj (j为排在i后元素,Txi为Xi所在上述方程式左侧时,该方程式中的常量,如Tx2=4)

(如:排列X1X3X7,满足条件
X1+3≤X3
X3+5≤X7 )

求满足方程组时,m+n最小时的排列.

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

vlphv

2 主题	4 听众	139 积分

升级 19.5%

该用户从未签到

2^#

发表于 2010-9-9 19:31 |只看该作者 |招呼Ta 关注Ta

laile.....................

我也说一句

发表

使用道具举报

chendongyi

0 主题	4 听众	304 积分

升级 1.33%

TA的每日心情

	开心 2014-1-1 12:58

签到天数: 16 天

[LV.4]偶尔看看III

3^#

发表于 2010-9-9 19:51 |只看该作者 |招呼Ta 关注Ta

学习学习!!!

我也说一句

发表

使用道具举报

kelenanhai

0 主题	3 听众	67 积分

升级 65.26%

该用户从未签到

自我介绍: 真诚与大家一道共同探讨,共同进步.

4^#

发表于 2010-9-9 19:57 |只看该作者 |招呼Ta 关注Ta

..............................................

我也说一句

发表

使用道具举报

sigma

0 主题	2 听众	77 积分

升级 75.79%

该用户从未签到

5^#

发表于 2010-9-9 20:00 |只看该作者 |招呼Ta 关注Ta

楼主，你的高尚情.太让人感动了。在现在这样一个物欲横流的金钱社会里，竟然还能见到楼主这样的性情中人，无疑是我这辈子最大的幸运。让我深深感受到了人性的伟大。楼主的帖子，就好比黑暗中刺裂夜空的闪电，又好比撕开乌云的阳光，一瞬间就让我如饮甘露，让我明白了永恒的真理在这个世界上是真实存在着的。只有楼主这样具备广阔胸怀和完整知识体系的人，才能作为这真理的惟一引言者。