还有房子会出来么？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Living

还有房子会出来么？

还有房子会出来么？# Living

B*12011-04-19 07:04

1 楼

Given an set of n integers and an integer x. Design an algorithm to check
whether k integers add up to x in the given set.
The complexity should be O(n^(k-1) * logn)

x*i2011-04-19 07:04

2 楼

现在还没过房子上市的旺季吧？愁死了，可心的房子怎么那么难找啊。

d*d2011-04-19 07:04

3 楼

从他时间要求上来看,是要你k-1重循环,或者k-1层递归,弄出个k-1个数的和,
然后再array里头binary search或者bst里头search剩下那点.

c*w2011-04-19 07:04

4 楼

Programming Pearls里面Column2, Problem8有这道题.
用Random_Select找出the kth element. Check数组前K个元素的和
是不是<=X, if yes, return true, otherwise return false.
因为Random_Selection算法之后, 数组的数据分布是: K个数之前的,都小于A[k], K个
数之后的,都大于A[k].
所以, 如果前K个数不<=X, 那么就肯定找不到其他K个数<=X了.
不过复杂度是O(n)

【在 B*******1 的大作中提到】

: Given an set of n integers and an integer x. Design an algorithm to check
: whether k integers add up to x in the given set.
: The complexity should be O(n^(k-1) * logn)

k*n2011-04-19 07:04

5 楼

otherwise没法return false。

【在 c*******w 的大作中提到】

: Programming Pearls里面Column2, Problem8有这道题.
: 用Random_Select找出the kth element. Check数组前K个元素的和
: 是不是<=X, if yes, return true, otherwise return false.
: 因为Random_Selection算法之后, 数组的数据分布是: K个数之前的,都小于A[k], K个
: 数之后的,都大于A[k].
: 所以, 如果前K个数不<=X, 那么就肯定找不到其他K个数<=X了.
: 不过复杂度是O(n)