华师一附中OI组

标题: 求数组中的第K大元素 [打印本页]
作者: diggersun    时间: 2015-11-1 13:17
标题: 求数组中的第K大元素
本帖最后由 diggersun 于 2015-11-1 13:30 编辑

给定一个数组，求其中第K大的元素。

若K=1，是求最大的元素，一般的做法是假设A0最大，然后从A1到 An逐个和他比较，大的留下来，最后留下来的就是最大的元素，我称之为打擂台方式。


若K=2，是求次大的元素，一般的做法是先比较A0和A1，求出最大次大，然后从A2到 An逐个和他们比较，有三种情况，对应三种决策，比最大的大，介于最大和次大之间，比次大的还小。这样也是一种打擂台方式。只是留在台上的是两个人而不是一个。


若K比较大呢？有的同学想现将数组排序，然后直接输出第K大，这样做很是浪费，一个改进的做法是选择排序选择到第K次的时候，或者冒泡排序冒到第K次的时候就不再继续了。


以选择排序为例，第一轮选择实际上将当前最小（大）的数字和数组的第一个数字进行交换，那么，等到第K个数字完成交换后，其实第K小（大）已经求出，无需基础排完整个数组。

有一种分治的思想很重要，可以用来解决这一类的问题，我们这里详细说说：
1、将数组的首元素作为划分元素X，从数组后面开始，每次找到一个比X小的数字，我们把它和X换，相当于换到了前面，然后从前面找到比X大的数字，和X交换，相当于往后面换，直到指针交错无法交换为止，这样，一轮交换后，X到了某个位置，它前面数字都比它小，后面的数字都比它大。
2、假设X的位置Y刚好是第K，那么问题解决了，若Y>k，说明要到前面找，若Y<K，说明要到前面去找，直到Y==k

这样做的话，对于K比较大是很有利的，因为每次几乎都是减半，快于每次减1。前面选择排序或者冒泡，下次查找只比上一次少了一个元素，减少的有限。

作者: diggersun    时间: 2015-11-1 23:09
  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4. int a[20]= {10,1,7,3,5,9,8,2,6,4,11,13,25,19,17,20,12,18,16,15};
  5. int partion(int *a,int l,int r)
  6. {
  7.     int p=a[l];//划分元素定为A[l]
  8.     while(l<r)
  9.     {
  10.         while((a[r]>=p)&&(l<r))r--;//后面找比P小的数
  11.         a[l]=a[r];
  12.         while((a[l]<=p)&&(l<r))l++;//前面找比P大的数
  13.         a[r]=a[l];
  14.     }
  15.     a[l]=p;return l;
  16. }

  18. int main()
  19. {
  20.     int x=8;//其实是求第8小，最小的是第0小
  21.     int l=0,r=19;
  22.     bool bb=true;
  23.     int t;
  24.     do
  25.     {
  26.         t=partion(a,l,r);// 得到划分元素的位置
  27.         if (t>x)r=t-1;  //若位置比x大，说明第X小的在前面
  28.         else if (t<x)l=t+1;//到后面去找
  29.         else bb=false;//相等表示找到了
  30.     } while (bb);
  31.     cout<<a[x]<<endl;
  32.     return 0;
  33. }
复制代码
作者: admin    时间: 2018-4-14 20:30
  1. #include <iostream>
  2. using namespace std;
  3. const int mm=10;
  4. int a[mm];
  5. int i;
  6. int hf(int l,int r)
  7. {
  8.     int p=a[l];
  9.     while (l<r)
  10.     {
  11.         while ((a[r]>=p) &&(l<r) ) r--;  ///一定是先从右边找小的
  12.         a[l]=a[r];
  13.         while ((a[l]<=p) &&(l<r) ) l++;  ///再从左边找大的
  14.         a[r]=a[l];
  15.     }
  16.     a[l]=p;
  17.     return l;
  18. }

  20. int get(int x,int l,int r)
  21. {
  22.     int p=hf(l,r);
  23.     if (p==x) return a[x];
  24.     else if (p>x) return  get(x,l,p-1);
  25.     else return get(x,p+1,r);
  26. }

  28. int main()
  29. {
  30.     ///在很顺序的里面找
  31.     for (i=0; i<=9; i++) a[i]=i;
  32.     for (i=0; i<=9; i++) cout<<get(i,0,9)<<' ';

  34.     cout<<endl;
  35.     ///在倒序中找
  36.     for (i=0; i<=9; i++) a[i]=9-i;
  37.     for (i=0; i<=9; i++) cout<<get(i,0,9)<<' ';

  39.     cout<<endl;
  40.     ///在相同的中找
  41.     for (i=0; i<=9; i++) a[i]=1;
  42.     for (i=0; i<=9; i++) cout<<get(i,0,9)<<' ';

  44.     ///在部分相同的中找
  45.     cout<<endl;
  46.     for (i=0; i<=9; i++) a[i]=10-i%2;
  47.     for (i=0; i<=9; i++) cout<<get(i,0,9)<<' ';

  49.     ///在乱序的中找
  50.     cout<<endl;
  51.     for (i=0; i<=9; i++) a[i]=i*i%10;
  52.     for (i=0; i<=9; i++) cout<<get(i,0,9)<<' ';
  53.     ///请体会此中的测试技巧
  54.     return 0;
  55. }
复制代码
作者: admin    时间: 2018-4-14 20:32
二楼的是以前对我校高中生讲的，写的是非递归的，很精妙，三楼的是递归的，很容易想到，建议初学者先学三楼的做法。



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2