一个martrix，每行每列都是sorted，找到前kth 个
Analysis:
Applying a quick-select algorithm will achieve an O( n * n ) time
complexity. Can we do better? Yes. Here is a algorithm:
1. Like quick-select algorithm, this algorithm applies divide-and-
conquer.
2. Initialize those two boundary lines to (n * [0] and n * [n]) to
include all array items in boundary.
3. Process subarray between boundary lines (lo, hi ) in each
recursive call:
a. select a random item in subarray and use it as pivot.
b. draw a new boundary line (lt) to separate item < pivot
and item >= pivot. Find the number of items < pivot (nLt)
c. draw a new boundary line (gt) to separate item <= pivot
and item > pivot. Find the number of items > pivot(nGt)
d. if k < nLt, recursively process subarray between
boundary (lo, lt)
e. if k >= nGt, recursively process subarray between
boundary (gt, hi)
d. else return pivot value
Step a, b, c, all takes O( n ) time. So the entire algorithm takes
O( n log(n ) )
class Solution
{
public:
int select( const vector >& arr, int k ) const
{
srand( time( 0 ) );
if( arr.empty() || arr[0].empty() || k < 0 || k >= arr.size() * arr[
0].size() )
throw "No solution";
vector vctLo( arr.size(), 0 );
vector vctHi( arr.size(), arr[0].size() );
return select( arr, k, vctLo, 0, vctHi, arr.size() * arr[0].size() );
}
private:
int select( const vector >& arr, int k, const vector&
vctLo,
int nLo, vector& vctHi, int nHi ) const
{
// Get a random item between lower and upper bound lines
int nPivot = getPivot( arr, vctLo, nLo, vctHi, nHi );
// 3-way Partition
vector vctLt = vctHi, vctGt = vctHi;
// nLt: number of item < pivot, nGt: number of item > pivot
int nLt = 0, nGt = 0;
for( int x=0; x{
if( x > 0 )
{
vctLt[x] = vctLt[x-1];
vctGt[x] = vctGt[x-1];
}
while( vctLt[x] > vctLo[x] && arr[x][vctLt[x]-1] >= nPivot ) --
vctLt[x];
while( vctGt[x] > vctLo[x] && arr[x][vctGt[x]-1] > nPivot ) --
vctGt[x];
nLt += vctLt[x];
nGt += vctGt[x];
}
if( k < nLt ) return select( arr, k, vctLo, nLo, vctLt, nLt );
if( k >= nGt ) return select( arr, k, vctGt, nGt, vctHi, nHi );
return nPivot;
}
int getPivot( const vector >& arr, const vector& vctLo,
int nLo,
const vector& vctHi, int nHi ) const
{
int x = 0;
while( vctLo[x] == vctHi[x] ) ++x;
int nIndex = rand() % (nHi - nLo);
while( nIndex >= vctHi[x] - vctLo[x] )
{
nIndex -= vctHi[x] - vctLo[x];
++x;
}
return arr[x][vctLo[x]+nIndex];
}
};
