「年齡記錄」數據結構

Question

我一直在尋找一種像年齡記錄列表一樣工作的數據結構。如果沒有一個年輕人有更高的分數，那麼你就有一個年齡記錄。因此，我想要一個對（a，b）的列表，其中對於所有對（a1，b1）和（a2，b2）中的所有對（在蘊涵之後）成立a1> a2 => b1> b2。

如果不存在一對（a_k，b_k）使得a_k不是a_new而是b_k> b_new，則應該存在插入（a_new，b_new）的插入方法插入（a_new，b_new）。如果滿足該條件，則插入新對，並從列表中刪除所有a_k> a_new，但刪除b_k。

數據結構不需要支持刪除。

Answer 1

以下是我認爲能爲您完成這項工作的通用解決方案。它沒有針對性能進行優化，也沒有特別好的測試。

public class AgePair<T, Y> 
    where T : IComparable<T> 
    where Y : IComparable<Y> 
{ 
    public T A { get; set; } 

    public Y B { get; set; } 
} 

public class AgeRecordList<T, Y> : IEnumerable<AgePair<T,Y>> 
    where T : IComparable<T> 
    where Y : IComparable<Y> 
{ 
    private List<AgePair<T, Y>> m_List = new List<AgePair<T, Y>>(); 

    public void Add(T a, Y b) 
    { 
     AgePair<T, Y> newPair = new AgePair<T, Y> { A = a, B = b }; 

     // Get all elements that are younger 
     var younger = GetYounger(newPair.A); 

     // Find any of the younger with a higher score 
     // If found, return without inserting the element 
     foreach (var v in younger) 
     { 
      if (v.B.CompareTo(newPair.B) >= 0) 
      { 
       return; 
      } 
     } 

     // Cache elements to delete 
     List<AgePair<T, Y>> toDelete = new List<AgePair<T, Y>>(); 

     // Find all the elder elements  
     var elder = GetElder(newPair.A); 

     // Find all elder elements with a lower B 
     foreach (var v in elder) 
     { 
      if (v.B.CompareTo(newPair.B) <= 0) 
      { 
       // Mark for delete 
       toDelete.Add(v); 
      } 
     } 

     // Delete those elements found above 
     foreach (var v in toDelete) 
     { 
      m_List.Remove(v); 
     } 

     // Add the new element 
     m_List.Add(newPair); 

     // Sort the list (ascending by A) 
     m_List.Sort(CompareA); 
    } 

    private List<AgePair<T, Y>> GetElder(T t) 
    { 
     List<AgePair<T, Y>> result = new List<AgePair<T, Y>>(); 

     foreach (var current in m_List) 
     { 
      if (t.CompareTo(current.A) <= 0) 
      { 
       result.Add(current); 
      } 
     } 

     return result; 
    } 

    private List<AgePair<T, Y>> GetYounger(T t) 
    { 
     List<AgePair<T, Y>> result = new List<AgePair<T, Y>>(); 

     foreach (var current in m_List) 
     { 
      if (t.CompareTo(current.A) > 0) 
      { 
       result.Add(current); 
      } 
     } 

     return result; 
    } 

    private static int CompareA(AgePair<T,Y> item1, AgePair<T,Y> item2) 
    { 
     return item1.A.CompareTo(item2.A); 
    } 


    public IEnumerator<AgePair<T, Y>> GetEnumerator() 
    { 
     return m_List.GetEnumerator(); 
    } 

} 

編輯1：算法的高級概述

1. 找到所有年輕或等於元素，
2. 對於所有年輕的或相同的元件，看是否有一個以上B
3. 如果（2）返回
4. 查找所有老年人元素
5. 如果任何老年人元素得分較低，請刪除
6. 排序列表按升序（按A）

編輯2：速度可以很容易地通過增加），一旦你找到了年輕的元素，你可以從該點尋找老人元素，而不是在繼續b）不用使用List的排序方法對它排序，而是使用InsertAt（0或第一個長輩的索引）

Answer 2

這個AgeList跟蹤每個年齡的最佳記錄，然後忽略當被問及獲勝者時，他們沒有年齡記錄。

雖然並非所有的輸家在插入時都被刪除（不確定這是否是一個強大的要求），但它應該通過懶惰來節省時間。 OrderBy的最大弱點是呼叫。如果在空間可用的情況下這種排序過於昂貴，可能會彈出一個SortedList來保存所有插入的a。

如果在時間可用的情況下空間有限，那麼編寫類似於GetWinners方法的清理方法很簡單。甚至可以在InsertMethod中調用以在每次插入後清理。

public class AgeList<T, U> where T:IComparable<T> where U:IComparable<U> 
{ 
    Dictionary<T, U> store = new Dictionary<T, U>(); 

    public void Insert(T a, U b) 
    { 
     if (!store.ContainsKey(a) || store[a].CompareTo(b) < 0) 
     { 
      store[a] = b; 
     } 
     //else discard by doing nothing 
    } 

    public IEnumerable<KeyValuePair<T, U>> GetWinners() 
    { 
     bool first = true; 
     U record = default(U); 
     foreach(T key in store.Keys.OrderBy(t => t)) 
     { 
      U newValue = store[key]; 
      if (first) 
      { 
       first = false; 
       record = newValue; 
       yield return new KeyValuePair<T, U>(key, record); 
      } 
      else if (record.CompareTo(newValue) < 0) 
      { 
       record = newValue; 
       yield return new KeyValuePair<T, U>(key, record); 
      } 
     } 
    } 
}