C++（2） 第k大元素

问题描述输入输出思路分析代码实现举例感想

问题描述

求出已知n个正整数中的第k大元素。（1<=k<=n）

输入

6 3 4 2 1 5 7 6

输出

1

思路分析

对于正整数序列 a [ n ]，我们可以设置两层 for 循环： 第一层用 n-i 标记第 i 大元素的下标（i 从1至k），第二层用 j 标记需要（与下一个元素）比较的元素的下标（0 ~ i -1）。通过内层循环，当前的最大元素被存储在 a [ i ] 中；通过外层循环，我们可以依次得到第 i 大元素 a [ n-i ] 。 该方法基于冒泡排序实现，明显看到，此方法时间复杂度为O(n²)。但由于外层循环次数由 n 减少到了 k，相当于只获得了排序后的后 k 位元素，相比于先排序后取值来说，一定程度上减少了运行时间。

代码实现

#include <iostream> using namespace std; int main() { int a[1000]={0}; int n; int k; cout<<"元素总个数："; cin>>n; cout<<"各元素分别为："; for(int i=0;i<n;i++) { cin>>a[i]; } cout<<"k为："; cin>>k; for(int i=n-1;i>=n-k;i--) // i记录第1大至第k大元素的下标 { for(int j=0;j<i;j++) // j记录需要（与下一个元素）比较的元素的下标 { if(a[j]>a[j+1]) // 由小到大排列 { int temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } cout<<"第k大元素为："<<a[n-k]<<endl; system("pause"); return 0; }

举例

感想

冫中！