“年龄记录”数据结构

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); 
      } 
     } 
    } 
}