问题:设有一组N个数而要确定其中第k个最大者。
solution 0:
最简单的方法当然就是将N个数读进数组里头,然后降序排序,返回a[k-1]即可。
solution 1:
把前k个元素读入数组,并以降序排序。接着,将剩下的元素逐个读入。当新元素被读到时,如果它小于数组中的第k个元素则忽略,否则将其放到正确的位置,同时将数组的最后一个元素挤出数组。当算法终止时,位于第k个位置的元素即为所求。
实现如下:
void bubble_sort(int a[], int len) //dscreamnet
{
for (int i = 0; i < len - 1; i++)
{
bool flag = false;
for (int j = len - 1; j > i ; j--)
{
if (a[j] > a[j-1])
{
int temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
flag = true;
}
}
if (false == flag)
{
return;
}
}
}
int main()
{
std::cout << "please input k :";
int max_k;
std::cin >> max_k;
std::cout << "please input k values :";
int *p = new int[max_k];
if (NULL == p)
{
std::cout << "new failed" << std::endl;
return 0;
}
for (int i = 0; i < max_k; i++)
{
std::cin >> p[i];
}
bubble_sort(p, max_k);
int other;
std::cout << "please input others, end with -1:";
while (std::cin >> other && other != -1)
{
int i = 0;
for (; i < max_k; i++)
{
if (p[i] < other)
{
break;
}
}
if (i >= max_k)
{
continue;
}
for (int j = max_k - 1; j > i; j--)
{
p[j] = p[j-1];
}
p[i] = other;
}
std::cout << p[max_k-1] << std::endl;
return 0;
}
solution 1相比solution 0,空间上省了一些,但时间消耗明显要大一些。