面接100問-2

このテーマはブログからhttp://zhedahht.blog.163.com/blog/static/25411174201131184017844/
アルゴリズム能力を強化する単純な目的からだ.
 
完全なタイトルの説明:
ある会社には数万人の従業員がいますが、時間の複雑さがO(n)のアルゴリズムでその会社の従業員の年齢をソートしてください.
O(1)のアシストスペースが使用可能
 
考え方:1.要求される時間の複雑さから見ると安定したソートであるべきである
      2.従業員の年齢は一般的に20-60歳の間に集中して分布しており、セグメントソートを考慮して集計することができるが、O(n)に合わない
      3.処理するデータは比較的に大きく、よくある手段はビット演算、カウント配列などである.
      4.補助空間がO(1)であることの理解
 
開始コード:(書き込み機能実装部のみ)

  
  
  
  

   
   
   
   
void SortAge(int employeesum, int *employee) { 
   
   
   
   
 
   
   
   
   
     

   
   
   
   
    int length = 70; 

   
   
   
   
    int *employee_age_num = new int[length]; 
   
   
   
   
 

   
   
   
   
    //First,initialize the array 
   
   
   
   
 
   
   
   
   
    for(int i = 0; i< length; i++) 
   
   
   
   
 
   
   
   
   
        employee_age_num[i] = 0; 
   
   
   
   
  
   
   
   
   
 
   
   
   
   
    //Scan the employees age information and record it 
   
   
   
   
 
   
   
   
   
    for(int i = 0; i < employeesum; i++)  
   
   
   
   
 
   
   
   
   
        employee_age_num[employee[i].age - 20]++; 
   
   
   
   
  
   
   
   
   
 
   
   
   
   
    //Sort the employee array by the record information  
   
   
   
   
 
   
   
   
   
    int employee_index = 0; 
   
   
   
   
 
   
   
   
   
    for(int i = 0 ; i < length; i++) 
   
   
   
   
 
   
   
   
   
        for(int j = 0; j < employee_age_num[j]; j++) { 
   
   
   
   
 
   
   
   
   
            //.....Swap the employee information including age and other things 
   
   
   
   
 
   
   
   
   
            employee_index++;    
   
   
   
   
 
   
   
   
   
        } 
   
   
   
   
 

   
   
   
   
    delete []emplyee_age; 
   
   
   
   
 
   
   
   
   
} 
  
  
  
  

 
分析:上のコードの书き込みの比较的に失败して、原因はテーマの意味をはっきりさせていないためです
      1.社員全体の情報を並べ替えるのではなく、社員の年齢を並べ替える.
        そのため、頭の中で構築されているのは、従業員情報が構造であり、全体的な情報をソートする必要があることです.
      2.O(1)の補助空間を用いて、最初は1つの大きさの空間しか申請できないと理解していたが、O(1)の意味は
        空間の大きさは定数で、Nの変化に従って変化しないで、ここの1は定数を表して、
      3.パラメータに異常処理を行わず、constに設定すべき変数があり、コードの頑丈性の考慮が足りない.
 
修正後のコード:
ここのemployee配列は従業員の年齢だけが格納されています.
 

  
  
  
  

   
   
   
   
bool SortAge(int employeesum, int *employee) { 

   
   
   
   
     
   
   
   
   
 
   
   
   
   
    if(employee == NULL || employeesum <= 0) 
   
   
   
   
 
   
   
   
   
        return false; 
   
   
   
   
         
   
   
   
   
 
   
   
   
   
    const int length = 70; 
   
   
   
   
 
   
   
   
   
    int *employee_age_num = new int[length]; 
   
   
   
   
 
   
   
   
   
 

   
   
   
   
    //First,initialize the array 
   
   
   
   
 
   
   
   
   
    for(int i = 0; i< length; i++) 
   
   
   
   
 
   
   
   
   
        employee_age_num[i] = 0; 
   
   
   
   
  
   
   
   
   
 
   
   
   
   
    //Scan the employees age information and record it 
   
   
   
   
 
   
   
   
   
    for(int i = 0; i < employeesum; i++)  
   
   
   
   
 
   
   
   
   
        employee_age_num[employee[i] - 20]++; 
   
   
   
   
 
   
   
   
   
     
   
   
   
   
 
   
   
   
   
    //Sort the employee array by the record information  
   
   
   
   
 
   
   
   
   
    int employee_index = 0; 
   
   
   
   
 
   
   
   
   
    for(int i = 0 ; i < length; i++) 
   
   
   
   
 
   
   
   
   
        for(int j = 0; j < employee_age_num[j]; j++) { 
   
   
   
   
 
   
   
   
   
            employee[employee_index] = i; 
   
   
   
   
 
   
   
   
   
            employee_index++;    
   
   
   
   
 
   
   
   
   
        } 
   
   
   
   
 

   
   
   
   
    delete []emplyee_age; 

   
   
   
   
 
   
   
   
   
    return true; 
   
   
   
   
 
   
   
   
   
} 
  
  
  
  

 
拡張:従業員の年齢に応じて、従業員全体の情報をソートする場合は?
     (コード中のemployee[employee_index]=iを、対応する位置の従業員情報と全体的に交換し、
       しかしflyingheartsが言ったように、N個のフラグビットタグ要素がアクセスされたかどうかは、ソートも不安定になります)
まとめ:1.面接問題ははっきり見て、異なる条件の制限、解決方法も違います.
      2.コードは先に機能を実現して段階的に最適化しているはずだが、そのために境界条件の検出を忘れないでください.
      3.功力はまだ浅いので、勉強を強化しなければならない.