摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法:(1)STL(2)快排+二分搜尋(3)HASH TABLE(資料結構)

在此提供 作法(2) 我不會STL 不會資料結構 *(第1個程式碼)                 

                              加快版(第2個程式碼)(優化輸入)

                              內建快排版(第4個程式碼)(比較慢)

感謝andy3466提供作法(3) (第3個程式碼) (別叫我解說 我不會嘿)
感謝teching 提供作法(2) (第4個程式碼部分資料)
感謝pcsh710742提供作法(1) (第5個程式碼 此為C++才有)

由於>10萬的手動快排 (void可能會爆掉 stack over)
所以要用內建的 不過要怎麼一次移兩個呢? 請看下面的程式碼(4)

/*********************************************************/

#include<stdio.h>
#include<stdlib.h>
int partition(int[], int, int);   
void quicksort(int[], int, int);
int num[100000]={0},L[100000]={0};
int index1(int n,int L)  
{  
 int lower=0, mid, high=L-1;  
 int index=-1;  
    do   /*二分搜尋*/ 
    {  
      mid=(lower+high)/2;  
      if(num[mid]<n)     lower=mid+1;  
      else if(num[mid]>n)  high=mid-1;  
      else  index=mid;  
    }  
    while(index==-1&&lower<=high);  
  return index;  
} 
main()
{
 int t,n,m,k,a,b;
 scanf("%d",&t);
 while(t--)
    {
       scanf("%d %d",&n,&k);
      
       for(a=0;a<n;a++)
        {
         scanf("%d",&num[a]);
         L[a]=a;
        }
       quicksort(num,0,n-1);
       for(a=0;a<k;a++)
         {
           scanf("%d",&m);
           int index=index1(m,n);
           printf("%d\n",L[index]+1);
         }
    }
 system("pause");
}
int partition(int num[],int left,int right)   
{  
  int a=left-1,b,s=num[right];  
  for(b=left;b<right;b++)  
   {  
     if(num[b]<s)  
       {  
         a++;  
         int temp,temp1;  
         temp=num[a];  
         temp1=L[a];
         num[a]=num[b];  
         L[a]=L[b];
         num[b]=temp;   
         L[b]=temp1;
       }   
   }   
         int temp,temp1;  
         temp=num[a+1];
         temp1=L[a+1];  
         num[a+1]=num[right];  
         L[a+1]=L[right];
         num[right]=temp;
         L[right]=temp1;   
   return a+1;   
}   
void quicksort(int num[],int left,int right)  
{  
 int q;  
 if(left<right)   
   {  
     q=partition(num,left,right);  
     quicksort(num,left,q-1);  
     quicksort(num,q+1,right);   
   }   
}

/*********************************************************/

#include<stdio.h>
#include<stdlib.h>
int partition(int[], int, int);   
void quicksort(int[], int, int);
int num[100000]={0},L[100000]={0};
int index1(int n,int L)  
{  
 int lower=0, mid, high=L-1;  
 int index=-1;  
    do   /*二分搜尋*/ 
    {  
      mid=(lower+high)/2;  
      if(num[mid]<n)     lower=mid+1;  
      else if(num[mid]>n)  high=mid-1;  
      else  index=mid;  
    }  
    while(index==-1&&lower<=high);  
  return index;  
} 
int input()  
{  
  char cha;  
  int x=0;  
  while(cha=getchar())  
     if(cha!=' '&&cha!='\n') break;  
  x=cha-48;  
  while(cha=getchar())   
    {  
     if(cha==' '||cha=='\n') break;  
      x=x*10+cha-48;  
    }  
    return x;  
}
main()
{
 int t,n,m,k,a,b;
 scanf("%d",&t);
 while(t--)
    {
       scanf("%d %d",&n,&k);
      
       for(a=0;a<n;a++)
        {
         num[a]=input();
         L[a]=a;
        }
       quicksort(num,0,n-1);
       for(a=0;a<k;a++)
         {
           m=input();
           int index=index1(m,n);
           printf("%d\n",L[index]+1);
         }
    }
 return 0;
}
int partition(int num[],int left,int right)   
{  
  int a=left-1,b,s=num[right];  
  for(b=left;b<right;b++)  
   {  
     if(num[b]<s)  
       {  
         a++;  
         int temp,temp1;  
         temp=num[a];  
         temp1=L[a];
         num[a]=num[b];  
         L[a]=L[b];
         num[b]=temp;   
         L[b]=temp1;
       }   
   }   
         int temp,temp1;  
         temp=num[a+1];
         temp1=L[a+1];  
         num[a+1]=num[right];  
         L[a+1]=L[right];
         num[right]=temp;
         L[right]=temp1;   
   return a+1;   
}   
void quicksort(int num[],int left,int right)  
{  
 int q;  
 if(left<right)   
   {  
     q=partition(num,left,right);  
     quicksort(num,left,q-1);  
     quicksort(num,q+1,right);   
   }   
}

/***********************************************************/

#include<stdio.h>  
#include<stdlib.h>   
struct hash{  
           int num;  
           int th;  
           struct hash* list;  
           };  
int main()  
{  
 int t;  
 scanf("%d",&t);    
 while(t--)  
    {  
    int k,n,m,mod,tol=1;  
    scanf("%d%d",&n,&k);  
    short int check[99998]={0};  
    struct hash* head[99998];  
    struct hash* last;  
    struct hash* next;  
    int number;  
    while(n--)  
    {  
    scanf("%d",&number);  
    mod=number%99997;  
    if(check[mod]==0)  
    {  
    next=malloc(sizeof(struct hash));  
    head[mod]=next;  
    head[mod]->list=NULL;  
    head[mod]->th=tol;  
    head[mod]->num=number;  
    check[mod]=1;  
         }  
     else{  
          next=malloc(sizeof(struct hash));  
          last=head[mod];  
          while(last->list!=NULL)  
          last=last->list;  
          last->list=next;  
          next->num=number;  
          next->th=tol;  
          next->list=NULL;  
          }  
     tol++;  
     }  
    while(k--)  
    {  
    scanf("%d",&m);          
    mod=m%99997;  
    last=head[mod];  
    if(check[mod]!=0)  
    while(1)         
    {  
    if(last->num==m){  
                     printf("%d\n",last->th);  
                     break;  
                     }  
    last=last->list;  
    }    
     
              }  
   
   }  
  return 0;  
   } 

/***************************************************/

#include<stdio.h>
#include<stdlib.h>
struct node
{
   int num;
   int L;
}node[100000]={0};
int compare(const void *ele1, const void *ele2)  
{  
  struct node  *px,*py;  
 
  px=(struct node *)ele1;  
  py=(struct node *)ele2;  
  /* 由小排到大 */   
  if(px->num > py->num) return 1;  
  else return 0;    
}
int index1(int n,int L)  
{  
 int lower=0, mid, high=L-1;  
 int index=-1;  
    do   /*二分搜尋*/ 
    {  
      mid=(lower+high)/2;  
      if(node[mid].num<n)     lower=mid+1;  
      else if(node[mid].num>n)  high=mid-1;  
      else  index=mid;  
    }  
    while(index==-1&&lower<=high);  
  return index;  
} 
int input()  
{  
  char cha;  
  int x=0;  
  while(cha=getchar())  
     if(cha!=' '&&cha!='\n') break;  
  x=cha-48;  
  while(cha=getchar())   
    {  
     if(cha==' '||cha=='\n') break;  
      x=x*10+cha-48;  
    }  
    return x;  
}
main()
{
 int t,n,m,k,a,b;
 scanf("%d",&t);
 while(t--)
    {
       scanf("%d %d",&n,&k);
      
       for(a=0;a<n;a++)
        {
         node[a].num=input();
         node[a].L=a;
        }
       qsort(node,n-1,sizeof(struct node), compare);
       for(a=0;a<k;a++)
         {
           m=input();
           int index=index1(m,n);
           printf("%d\n",node[index].L+1);
         }
    }
 return 0;
}
/*********************************************************/

#include<iostream>
#include<map>
using namespace std;
int main(){
int t,n,k,i,l,m;
map <int, int> ans;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&k);
for(i=1; i<=n; i++){
scanf("%d",&m);
ans[m]=i;
}
for(i=0; i<k; i++){
scanf("%d",&l);
printf("%d\n",ans[l]);
}
}
}