B*******1
发帖数: 2454 | 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) | d*******d
发帖数: 2050 | 2 从他时间要求上来看,是要你k-1重循环,或者k-1层递归,弄出个k-1个数的和,
然后再array里头binary search或者bst里头search剩下那点. | c*******w
发帖数: 63 | 3 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****n
发帖数: 369 | 4 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)
| s****j
发帖数: 67 | 5 i think only O(n^2*k) is needed to solve this problem using a dp method,
similar to knapsack problem | s****j
发帖数: 67 | | j********x
发帖数: 2330 | 7 This is called pseudo poly time
And it behaves badly when x is large.
【在 s****j 的大作中提到】
: sorry, it's O(n*x*k)
| s****j
发帖数: 67 | 8 agree
just another method to mention~
【在 j********x 的大作中提到】
: This is called pseudo poly time
: And it behaves badly when x is large.
| r*******g
发帖数: 1335 | |
|
