寻找给定区间内第K小的数（分治递归）

给出一个长度为N的序列A1,A2,A3,...,AN，其中每项都是
小于10^5的自然数。
现在有M个询问，每个询问都是Ai...Aj中第k小的数等
于多少。
数据范围：
在60%的数据中，1≤N≤1000，1≤M≤1000
在100%的数据中，1≤N≤10000,1≤M≤2000

 

输入格式

第一行两个正整数N，M。
第二行N个数，表示序列A1,A2,...,AN。
紧着的M行，每行三个正整数i,j,k(k≤j-i+1)，表示
询问Ai...Aj中第k小的数等于多少。

输出格式

共输出M行，第i行输出第i个询问的答案。

sample input:

4 3
4 1 2 3
1 3 1
2 4 3
1 4 4

sample output:

1

3

4

 

      

      区间是给定的，所以先有必要先搞定这个问题：求一个数组第K小的数。分治递归，用快排的思想，于是我把快排重新敲了一遍，就开始敲一个数组（乱序）第K小的数。

      快排要把所有元素排成有序的，这个问题没有必要。以某个元素为中心，把比它的小的分到数组的左边，比它大的分到数组的右边。然后把这个元素的新位置与k-1比较（数组下标从0开始）,相等则返回，找到了。小于k-1，则在右边找，否则到左边找。典型的分治递归啊！

 

代码：

#include<stdio.h>
#include<stdlib.h>

int a[100];

int kth(int a[],int low,int high,int k);

int main()
{
  int n,k,i,j;
  
     while(scanf("%d%d",&n,&k) != EOF)
     {
       for(i = 0 ; i < n ;++i)
       scanf("%d",&a[i]);  
                          
       printf("第k小的数：%d\n",kth(a,0,n-1,k));
       
       printf("\n");
     }  
    
  system("pause");
  return 0;    
}
 
int kth(int a[],int low,int high,int k)
{
   int i,j,part;
   i = low;
   j = high;
   part = a[low];
   
     while(i<j)
     {
          while(i<j && a[j]>= part) --j;
          if(i<j) a[i++] = a[j];
          
          while(i<j && a[i]<part) ++i;
          if(i<j) a[j--] = a[i];
     }
     a[i] = part;
    
     if(k - 1 == i) return a[i];
     else
     {
        if(i < k) return kth(a,i+1,high,k);   
        else return kth(a,low,i-1,k); 
     }   
}
 
 

 

  然后非常高兴，改下参数不就可以AC上面那个题了吗？结果超时了。

超时代码：

#include<stdio.h>
#include<stdlib.h>

int a[10001];

int kth(int a[],int low,int high,int k);

int main()
{
  int n,ask,i,j,from,to,k;
  
     while(scanf("%d%d",&n,&ask) != EOF)
     {
       for(i = 0 ; i < n ;++i)
       scanf("%d",&a[i]);  
                          
         do
         {
            scanf("%d%d%d",&from,&to,&k);              
            printf("%d\n",kth(a,from-1,to-1,k));
                          
         }while(--ask); 
     }  
    
 // system("pause");
  return 0;    
}
 
int kth(int a[],int low,int high,int k)
{
   int i,j,part;
   i = low;
   j = high;
   part = a[low];
   
     while(i<j)
     {
          while(i<j && a[j]>= part) --j;
          if(i<j) a[i++] = a[j];
          
          while(i<j && a[i]<part) ++i;
          if(i<j) a[j--] = a[i];
     }
     a[i] = part;
    
     if(k - 1 == i) return a[i];
     else
     {
        if(i < k) return kth(a,i+1,high,k);   
        else return kth(a,low,i-1,k); 
     }   
}
 
 

　　

    算法是没有错了。就是不应该每次都去检索。否则肯定超时。

于是很无奈，看了周磊（算法天才啊！）的博客学习学习，他说用伴随数组可以做。

下面我们给出伴随数组解法，首先，定义一个结构体，一个是数组元素，另一个是数组原来的标号，记录每个数在数组的原顺序。

    我们以下面的测试数据举例（红体部分表示下标为2~5之间的数5,2,6,3，浅色部分表示数组中的数各自对应的数组下标，淡蓝色部分为给定的下标区间，注，这里，我们让数组下标从1开始）：

      a[i].data   1 5 2 6 3 7 4
      a[i].num   1 2 3 4 5 6 7 

    现在，题目给定了下标区间，如在原序列中下标2~5（即下标为2、3、4、5）区间找到第3小的数。问题亦相当于要你找原序列里给定下标区间即第2个数到第5个数之中（5 2 6 3）第3小的数（当然，答案很明显，第3小的数就是5）。

那么对原数组进行排序，然后得到的序列应该是（注：原下标始终保持不变）：

      a [i].data  1 2 3 4 5 6 7
      a [i].num  1 3 5 7 2 4 6

    如上，既然数据现在已经从小到大排好了，那么，我们只需要进行一次检索，从最小的数到最大的数，我们找第k(k=3)小的数，当我们发现下标a[i].num等于原给定下标区间在2~5中，即a[i].num==2 || 3 || 4 || 5的时候，k--，那么当k==0的时候，我们也就找到了第k(3)小的数了。如下（红色部分表示原给定下标区间中的数，浅色部分依然是原各数对应的下标，淡蓝色部分为原来给定的下标区间所对应的索引）：

      a [i].data   1 2 3 4 5 6 7
      a [i].num   1 3 5 7 2 4 6 
         k           3 2 1 1 0

 故下标索引为2~5之间第k（3）小的数是5。

    程序的构造与解释：由于排序后，我们能保证原序列已经从小到大的排好序了，所以，当遍历或扫描到原序列给定下标区间中的数时，则k--，最终能在k==0时，找到第k小的数，且这个数是在原来给定下标区间中的某一个数。
    而这个伴随数组，或者说原序列各数的索引则帮我们或者说是帮电脑记下了原来的数，已让我们后来遍历时能识别排序后序列中的数是否是给定下标区间中的某一个数。如果是原给定下标区间中的数，则k--，否则k不变。

代码：

#include <cstdio>  
#include <algorithm>  
#include <cstdlib>
using namespace std;  
  
struct node
{  
    int num,data;  
    bool operator < (const node &p) const   
    {  
        return data < p.data;  
    }  
};  
node p[10001];  
 
int main()  
{  
    int n,ask;  
    int i,j,a,b,k; 
      
    scanf("%d%d",&n,&ask);   
    for(i=1;i<=n;i++)   
    {  
        scanf("%d",&p[i].data);  
        p[i].num = i;  
    }  
    sort(p+1,p+1+n);    //调用库函数sort完成排序，复杂度n*logn  
   
      while(ask--)
      {
         scanf("%d%d%d",&a,&b,&k);  
         for(i=1;i<=n;i++)   //扫描一遍，复杂度n  
         {  
            if(p[i].num>=a && p[i].num<=b)   
               k--;   
            if(k == 0)    break;  
         }  
         printf("%d\n",p[i].data);  
      
      }
    
   // system("pause");
    return 0;  
}  

　　

 发现map的特性不是正好可以用来搞这个题吗？于是用map写了，测试数据正确，和上面AC代码算法一样。确得到WA。不知为什么。

WA代码（map）：

#include <map>
#include <iterator>
#include <cstdio>
#include <cstdlib>
using namespace std;

map<int ,int>m;
map<int ,int>::iterator iter;
 
int main()
{
  int i,n,con,ask,from,to,k;  
  scanf("%d%d",&n,&ask);
  
    for(i = 1 ; i <= n ; ++i)
    {
       scanf("%d",&con);
       m.insert(make_pair(con,i));
      // m[con] = i;     
    }
    
     while(ask--)
     {
       scanf("%d%d%d",&from,&to,&k);            
       
       for(iter = m.begin();iter != m.end(); ++iter)          
       {
          if(iter->second >= from && iter->second <= to)          
          --k;
          if(!k) break;       
       }
       
       printf("%d\n",iter->first);          
     }
          
  //system("pause");
  return 0;
}

      用map为什么是WA？有待解决!