Hi, Quintopia,
Maybe you misunderstood my algorithm above.
S_k is a set of ordered pair (i,j)
each time we pop the min(S_k) from S_k, we insert at most 2 element in
it
so its size is in O(k)
I think the following should be more clear:
heap: MIN_HEAP
visited[n][n] =
Hi, ljb,
Let me have a try to prove the correctness of it.
Let define a property A(S) :
S is a set of ordered pair (i,j), and every
pair (x,y) whose sum(x,y) is less than min{S} = sum(mi,mj) is already
output.
Initially, we have S_1 = {(1,1)}, A(S_1) holds.
Suppose that for n, A(S_n) holds,
If we have a set of S_k = {(i,j)} , such that every pair (x,y) whose
sum(x,y) max{Sk} is already output,
then the next one to output is min{Sk} = sum(mi,mj), then output it,
then we can obtain S_(k+1) = Sk \ {(mi,mj)} U {(mi,mj+1),(mi+1,mj)},
also for every pair (x,y) whose sum(x,y)min{S_(k+1)}
If we have a set S_k = {(i,j)} , such that every pair (x,y) whose
sum(x,y) min{Sk} is already output,
then the next one to output is min{Sk} = sum(mi,mj), output it.
we can obtain S_(k+1) = Sk \ {(mi,mj)} U {(mi,mj+1),(mi+1,mj)},
also for every pair (x,y) whose sum(x,y)min{S_(k+1)} is already
To find the 100th number in O(n) will do.
On 11月10日, 下午11时09分, [EMAIL PROTECTED]
[EMAIL PROTECTED] wrote:
I consider 3 ways:
n=1 million.
1. use a 100 heap (n*log(100)?)
2. use a 1 million heap.(time O(nlogn))
3. use quicksort, each time, discard the less part. ( O(logn)?)
but I can't
