w****x
发帖数: 2483 | 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;
} | p****e
发帖数: 3548 | 2 details of the question? | s*****1
发帖数: 134 | 3 我在想，如果不追求很快的话
这个好像也就是 M个sorted的序列，然后merge一下
和Leetcode 上 Merge k Sorted Lists 是不是差不多？ | w****x
发帖数: 2483 | 4
那个解法最差复杂度还不如全部selection sort
【在 s*****1 的大作中提到】
: 我在想，如果不追求很快的话
: 这个好像也就是 M个sorted的序列，然后merge一下
: 和Leetcode 上 Merge k Sorted Lists 是不是差不多？
| s*****1
发帖数: 134 | 5 复杂度是 K lg(M) 或 K lg(N) 看谁小,为什么比selection sort慢？
大牛请明示~ | w****x
发帖数: 2483 | 6
假如k是M*N,那么merge的复杂度就是M*N*logM
Selection sort是M*N
【在 s*****1 的大作中提到】
: 复杂度是 K lg(M) 或 K lg(N) 看谁小,为什么比selection sort慢？
: 大牛请明示~
| s*****1
发帖数: 134 | 7 恩，我看懂了，你说的是quick select~
我觉得你说的是有道理的~ | w****x
发帖数: 2483 | 8 做了一个QuadTree
struct PT
{
int x;
int y;
};
struct REC
{
POINT topLft;
POINT bottomRgt;
REC(int a, int b, int c, int d)
{
topLft.x = a;
topLft.y = b;
bottomRgt.x = c;
bottomRgt.y = d;
}
bool inRect(PT pt)
{
return pt.x >= topLft.x && pt.x <= bottomRgt.x
&& pt.y >= topLft.y && pt.y <= bottomRgt.y;
}
bool intersect(REC rect)
{
return min(bottomRgt.x, rect.bottomRgt.x) >= max(topLft.x, rect.
topLft.x)
&& min(bottomRgt.y, rect.bottomRgt.y) >= max(topLft.y, rect.
topLft.y);
}
};
struct QuadNode
{
static const int limit = 2;
QuadNode(REC& rc) : area(rc)
{
pTopLft = NULL;
pTopRgt = NULL;
pBottomLft = NULL;
pBottomRgt = NULL;
}
bool insert(int x, int y)
{
PT pt;
pt.x = x;
pt.y = y;
if (!area.inRect(pt))
return false;
if (m_pts.size() < limit)
{
m_pts.push_back(pt);
return true;
}
int nMidX = (area.topLft.x + area.bottomRgt.x)/2;
int nMidY = (area.topLft.y + area.bottomRgt.y)/2;
if (pTopLft == NULL)
pTopLft = new QuadNode(REC(area.topLft.x, area.topLft.y, nMidX,
nMidY));
if (pTopRgt == NULL)
pTopRgt = new QuadNode(REC(nMidX, area.topLft.y, area.bottomRgt.
x, nMidY));
if (pBottomLft == NULL)
pBottomLft = new QuadNode(REC(area.topLft.x, nMidY, nMidX, area.
bottomRgt.y));
if (pBottomRgt == NULL)
pBottomRgt = new QuadNode(REC(nMidX, nMidY, area.bottomRgt.x,
area.bottomRgt.y));
if (pTopLft->insert(x, y)) return true;
if (pTopRgt->insert(x, y)) return true;
if (pBottomLft->insert(x, y)) return true;
if (pBottomRgt->insert(x, y)) return true;
return false;
}
void getPoits(REC rect, vector& res)
{
if (!area.intersect(rect))
return;
for (vector::iterator it = m_pts.begin(); it != m_pts.end(); it+
+)
{
if (rect.inRect(*it))
res.push_back(*it);
}
if (NULL != pTopLft)
pTopLft->getPoits(rect, res);
if (NULL != pTopRgt)
pTopRgt->getPoits(rect, res);
if (NULL != pBottomLft)
pBottomLft->getPoits(rect, res);
if (NULL != pBottomRgt)
pBottomRgt->getPoits(rect, res);
}
REC area;
vector m_pts;
QuadNode* pTopLft;
QuadNode* pTopRgt;
QuadNode* pBottomLft;
QuadNode* pBottomRgt;
}; |
|
