2013
12-10

# 面试题精选100题(05)－查找最小的k个元素[算法]

typedef multiset<int, greater<int> >  IntHeap;

///////////////////////////////////////////////////////////////////////
// find k least numbers in a vector
///////////////////////////////////////////////////////////////////////
void FindKLeastNumbers
(
const vector<int>& data,               // a vector of data
IntHeap& leastNumbers,                 // k least numbers, output
unsigned int k
)
{
leastNumbers.clear();

if(k == 0 || data.size() < k)
return;

vector<int>::const_iterator iter = data.begin();
for(; iter != data.end(); ++ iter)
{
// if less than k numbers was inserted into leastNumbers
if((leastNumbers.size()) < k)
leastNumbers.insert(*iter);

// leastNumbers contains k numbers and it's full now
else
{
// first number in leastNumbers is the greatest one
IntHeap::iterator iterFirst = leastNumbers.begin();

// if is less than the previous greatest number
if(*iter < *(leastNumbers.begin()))
{
// replace the previous greatest number
leastNumbers.erase(iterFirst);
leastNumbers.insert(*iter);
}
}
}
}

1. 事后队长暴打涉事队员：“上煎蛋阿辣！！上煎蛋阿辣！！搞队员阿辣！！！我没屎忽比你地屌咩？？？我屎忽窿感松咩？！？！”

2. 事后队长暴打涉事队员：“上煎蛋阿辣！！上煎蛋阿辣！！搞队员阿辣！！！我没屎忽比你地屌咩？？？我屎忽窿感松咩？！？！”

3. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

4. for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dp = dp [j-1] + 1;
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp = dp[i-1] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp = Math.max(dp [j - 1] + 1, dp );
}
}
这里的代码似乎有点问题？ dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

5. “再把所有不和该节点相邻的节点着相同的颜色”，程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

6. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge