hdu acm 1029

這題有三種解法：

1.利用hash表

2.先排序，然後通過一次遍歷，找出最長子串。

下面詳細介紹一下第3種方法：

先看源代碼：

[cpp]  #include <cstdio>    
 
int main()   
{   
      int ans, num, count, n;   
      while (scanf("%d", &n) != EOF)   
      {   
          count = 0;   
         for (int i=1; i<=n; i++)   
         {   
             scanf("%d", &ans);   
             if (count == 0)   
             {   
                 num = ans;   
                 count ++;   
             }   
             else    
               if (ans == num)   
                    count++;   
               else count--;   
         }   
         printf("%d\n", num);   
      }   
   return 0;      
}   

#include <cstdio> 

int main() 
{ 
      int ans, num, count, n; 
      while (scanf("%d", &n) != EOF) 
      { 
          count = 0; 
         for (int i=1; i<=n; i++) 
         { 
             scanf("%d", &ans); 
             if (count == 0) 
             { 
                 num = ans; 
                 count ++; 
             } 
             else  
               if (ans == num) 
                    count++; 
               else count--; 
         } 
         printf("%d\n", num); 
      } 
   return 0;    
}  解釋：這題比較特殊，根據題意數目最多整數的個數是大於等於N/2+1，也就是會超過其他整數的個數之和。

count保存的是目前出現次數最多的整數 減去 其他整數的個數。由於總個數為奇數，結果count一定>=1。