数学建模社区-数学中国

标题: 两个算法问题 [打印本页]

作者: ccf19881030 时间: 2010-9-9 19:28
标题: 两个算法问题
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最小时的排列.

作者: vlphv 时间: 2010-9-9 19:31
laile.....................

作者: chendongyi 时间: 2010-9-9 19:51
学习学习!!!

作者: kelenanhai 时间: 2010-9-9 19:57
..............................................

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

作者: dynamic 时间: 2010-9-9 20:00
很好！很强大！

作者: liaoweida 时间: 2010-9-9 20:08
学习学习!!!

作者: liaoweida 时间: 2010-9-9 20:08
很好！很强大！

作者: zhangzhangjj 时间: 2010-9-9 20:43
很好！很强大！

作者: echofly 时间: 2010-9-9 21:48
学习中哦~~~~~~~~~~

作者: nikki-webster 时间: 2010-9-9 22:28
很好很强大

作者: myhunterli 时间: 2010-9-10 08:00
我要把这个帖子一直往上顶，往上顶！

作者: dennis369 时间: 2010-9-10 11:39
试试运气啦~~~~~~~~~~~

作者: lilei 时间: 2010-9-10 11:51
顶顶更健康，越顶吃的越香。

作者: bbf 时间: 2010-9-10 12:00
来报道!!!!!!!!!!!

作者: shaoqin 时间: 2010-9-10 15:00
强人，佩服死了。呵呵，不错啊

作者: njtuwangrun 时间: 2010-9-10 20:00
楼主的帖子实在是写得太好了。可是我立刻想到，这么好的帖子，倘若别人看不到，那么不是浪费楼主的心血吗？经过痛苦的思想斗争，我终于下定决心，牺牲小我，奉献大我。我要拿出这帖子奉献给世人赏阅，我要把这个帖子一直往上顶，往上顶！顶到所有人都看到为止！

作者: net 时间: 2010-9-11 08:00
强烈支持。楼主万岁

作者: libin1984 时间: 2010-9-11 12:00
来报道!!!!!!!!!!!

作者: wbj 时间: 2010-9-11 15:00
哦～～

作者: lsrj 时间: 2010-9-11 20:00
我来了~~~~~~~~~ 闪人~~~~~~~~~~~~~~~~

作者: iamwuzhen 时间: 2010-9-12 08:00
顶顶更健康，越顶吃的越香。

作者: kallstrom 时间: 2010-9-12 12:00
鉴定完毕！

作者: zhyqmn 时间: 2010-9-12 15:01
楼主的帖子实在是写得太好了。可是我立刻想到，这么好的帖子，倘若别人看不到，那么不是浪费楼主的心血吗？经过痛苦的思想斗争，我终于下定决心，牺牲小我，奉献大我。我要拿出这帖子奉献给世人赏阅，我要把这个帖子一直往上顶，往上顶！顶到所有人都看到为止！

作者: xqsf 时间: 2010-9-12 20:00
楼主的帖子实在是写得太好了。可是我立刻想到，这么好的帖子，倘若别人看不到，那么不是浪费楼主的心血吗？经过痛苦的思想斗争，我终于下定决心，牺牲小我，奉献大我。我要拿出这帖子奉献给世人赏阅，我要把这个帖子一直往上顶，往上顶！顶到所有人都看到为止！

作者: dj919 时间: 2010-9-13 08:00
呵呵大家好奇嘛来观看下~~~~

作者: xujing100 时间: 2010-9-13 12:00
我要把这个帖子一直往上顶，往上顶！

作者: liwenhong 时间: 2010-9-13 15:00
楼主，你写得实在是太好了。我惟一能做的，就只有把这个帖子顶上去这件事了

作者: Rainhart_Xu 时间: 2010-9-13 20:00
我来了~~~~~~~~~ 闪人~~~~~~~~~~~~~~~~

作者: chesson 时间: 2010-9-14 08:00
强烈支持。楼主万岁

作者: chenrongle 时间: 2010-9-14 12:00
哦～～

作者: watchor 时间: 2010-9-14 15:00
鉴定完毕！

作者: hoverchang 时间: 2010-9-14 20:00
鉴定完毕！

作者: haiyuan 时间: 2010-9-15 08:00
我回不抢呢考虑再三还是不抢了吧 ^_^

作者: xzhuang 时间: 2010-9-15 12:00
试试运气啦~~~~~~~~~~~

作者: dfhe060 时间: 2010-9-15 15:00
我基本上是采用看英语文章的办法，先泛读，再精读，再一句一句看，最后再提纲挈领，总算是明白一点了，当然，也可能还是领悟错了。最后要说的一句话是：楼主，你很牛叉，希望你不是真的有病。

作者: yks2006 时间: 2010-9-15 20:00
哦～～

作者: arthuryuan 时间: 2010-9-15 20:00
楼主的帖子实在是写得太好了。可是我立刻想到，这么好的帖子，倘若别人看不到，那么不是浪费楼主的心血吗？经过痛苦的思想斗争，我终于下定决心，牺牲小我，奉献大我。我要拿出这帖子奉献给世人赏阅，我要把这个帖子一直往上顶，往上顶！顶到所有人都看到为止！

作者: wxp_builder 时间: 2010-9-16 12:00
看起来好~~像啊~~~~~

作者: duhaiming 时间: 2010-9-16 15:00
声明一下：本人看贴和回贴的规则，好贴必看，精华贴必回。

作者: huangyi317 时间: 2010-9-16 20:00
哦～～

作者: 漫步星空 时间: 2011-5-3 22:54
什么啊正的什么也没有

作者: chenxs008 时间: 2011-8-13 10:59
good ,thks

作者: shuxuezaozhuang 时间: 2011-9-14 20:17
谢谢你！！

作者: 乖乖1503155 时间: 2012-1-28 14:44
学过啦yeo

作者: 1221long 时间: 2014-4-10 17:08
真的挺难的~

作者: 499379348 时间: 2014-7-14 17:10
这么多回复却是“由题无解”..

作者: 模天大楼 时间: 2014-8-10 23:54
喜欢就收下了\(^o^)/~

作者: 流雨星月 时间: 2014-8-30 16:10
挺好的，顶一下

作者: LYJA 时间: 2015-5-20 20:28
楼主好人，谢谢！！！！！！！！！！！！！！！！！！！！！！

作者: 540136593 时间: 2018-3-21 14:05
不错不错学习了

作者: peter1977 时间: 2018-5-31 15:01
GOOGle 面试题还是有高度的。。。

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)