做了一下Kth small in young tablet 和 largest rectangle contain 1s# JobHunting - 待字闺中
w*x
1 楼
一直认为面试出这么难得题真是过分啊！！
================= kth element in young tablet (M+N)log(numeric range)
solution ===========
const int M = 4;
const int N = 4;
int getOrder(int A[M][N], int tg)
{
int c = 0;
int i = 0;
int j = N-1;
while (i < M && j >= 0)
{
if (A[i][j] >= tg)
j--;
else
{
c += j+1;
i++;
}
}
return c+1;
}
int getKthMin(int A[M][N], int k)
{
if (k <= 0 || k > M*N)
return INT_MIN;
int nBeg = A[0][0];
int nEnd = A[M-1][N-1];
int nPrev = 0;
int nCur = -1;
while (nCur != k)
{
int nMid = (nBeg+nEnd)/2;
nCur = getOrder(A, nMid);
if (nCur == nPrev)
break;
if (nCur > k)
nEnd = nMid;
if (nCur < k)
nBeg = nMid;
nPrev = nCur;
}
int nTg = (nBeg+nEnd)/2;
int i = 0;
int j = N-1;
int nRet = 0;
bool bFirst = true;
while (i < M && j >= 0)
{
if (A[i][j] == nTg)
return A[i][j];
if (A[i][j] > nTg && (bFirst || nRet - nTg > A[i][j] - nTg))
{
bFirst = false;
nRet = A[i][j];
}
if (A[i][j] > nTg)
j--;
else i++;
}
return nRet;
}
============= max 1s rectangle histogram solution ==========
/*Given a 2D binary matrix filled with 0's and 1's, find the largest
rectangle containing all ones and return its area.*/
const int M = 5;
const int N = 6;
int getMaxRect(int A[M][N])
{
int rec[M][N] = { 0 };
for (int col = 0; col < N; col++)
{
for (int row = M-1; row >= 0; row--)
{
if (A[row][col] == 0)
rec[row][col] = 0;
else
rec[row][col] = row == M-1 ? 1 : 1+rec[row+1][col];
}
}
int nRet = 0;
for (int row = 0; row < M; row++)
{
stack stk;
int nCurMax = 0;
for (int col = 0; col <= N; col++)
{
int nNum = col == N ? INT_MIN : rec[row][col];
while (!stk.empty() && nNum <= rec[row][stk.top()])
{
int top = stk.top();
stk.pop();
int nScope = stk.empty() ? top + 1 : top - stk.top();
nCurMax = max(nCurMax, nScope*rec[row][top]);
}
stk.push(col);
}
nRet = max(nRet, nCurMax);
}
return nRet;
}
================= kth element in young tablet (M+N)log(numeric range)
solution ===========
const int M = 4;
const int N = 4;
int getOrder(int A[M][N], int tg)
{
int c = 0;
int i = 0;
int j = N-1;
while (i < M && j >= 0)
{
if (A[i][j] >= tg)
j--;
else
{
c += j+1;
i++;
}
}
return c+1;
}
int getKthMin(int A[M][N], int k)
{
if (k <= 0 || k > M*N)
return INT_MIN;
int nBeg = A[0][0];
int nEnd = A[M-1][N-1];
int nPrev = 0;
int nCur = -1;
while (nCur != k)
{
int nMid = (nBeg+nEnd)/2;
nCur = getOrder(A, nMid);
if (nCur == nPrev)
break;
if (nCur > k)
nEnd = nMid;
if (nCur < k)
nBeg = nMid;
nPrev = nCur;
}
int nTg = (nBeg+nEnd)/2;
int i = 0;
int j = N-1;
int nRet = 0;
bool bFirst = true;
while (i < M && j >= 0)
{
if (A[i][j] == nTg)
return A[i][j];
if (A[i][j] > nTg && (bFirst || nRet - nTg > A[i][j] - nTg))
{
bFirst = false;
nRet = A[i][j];
}
if (A[i][j] > nTg)
j--;
else i++;
}
return nRet;
}
============= max 1s rectangle histogram solution ==========
/*Given a 2D binary matrix filled with 0's and 1's, find the largest
rectangle containing all ones and return its area.*/
const int M = 5;
const int N = 6;
int getMaxRect(int A[M][N])
{
int rec[M][N] = { 0 };
for (int col = 0; col < N; col++)
{
for (int row = M-1; row >= 0; row--)
{
if (A[row][col] == 0)
rec[row][col] = 0;
else
rec[row][col] = row == M-1 ? 1 : 1+rec[row+1][col];
}
}
int nRet = 0;
for (int row = 0; row < M; row++)
{
stack
int nCurMax = 0;
for (int col = 0; col <= N; col++)
{
int nNum = col == N ? INT_MIN : rec[row][col];
while (!stk.empty() && nNum <= rec[row][stk.top()])
{
int top = stk.top();
stk.pop();
int nScope = stk.empty() ? top + 1 : top - stk.top();
nCurMax = max(nCurMax, nScope*rec[row][top]);
}
stk.push(col);
}
nRet = max(nRet, nCurMax);
}
return nRet;
}
