剑指Offer 39：数组中出现超过一半的数字
解法一中提到Partition方法，出自快速排序
选中数组中随机一个数字，将小于它的数字排到左边，大于它的数字排到右边
int Partition(int data[], int length, int start, int end)
{
if (data == nullptr || length <= 0 || start < 0 || end >= length)
throw new std:exception("Invalid Parameters");
int i = RandomInRange(start, end);
Swap(&data[i], &data[end]);
// small代表最后一个小于选中数的位置
int small = start - 1;
for (i = start; i < end; i++)
{
if (data[i] < data[end])
{
small++;
// 中间有大于选中的数字
if (i != small)
Swap(&data[i], &data[small]);
}
}
// 这里small自增是为了交换大数和末尾的选中数字
small++;
Swap(&data[small], &data[end]);
return small;
}
使用以上的方法，可以类似二分的找到中位数，而中位数就是数组中超过一半的数，复杂度为
相关问题： 找到数组中第k大的数字，复杂度为
第二种解法保存两个数字，分别为当前数字以及连续出现次数
好处在于代码结构简单，且不修改原始数据
剑指Offer 40：最小的k个数
排序的复杂度为，使用Partition方法可以将复杂度降到
另一种解法是维护一个长度为k的池子，依次比较现有池子和下一个数字的大小关系，维护这个池子
typedef multiset<int, greater<int>> intSet;
typedef multiset<int, greater<int>>::iterator setIterator;
void GetLeastNumbers(const vector<int> &data, intSet& leastNumbers, int k)
{
leastNumbers.clear();
if (k < 1 || data.size() < k)
return;
vector<int>::const_iterator iter = data.begin();
for (; iter != data.end; iter++)
{
if (leastNumbers.size() < k)
{
leastNumbers.insert(*iter);
}
else if (leastNumbers.size() == k && *iter < *(leastNumbers.begin()))
{
leastNumbers.erase(leastNumbers.begin());
leastNumbers.insert(*iter);
}
}
}
