"年龄记录"数据结构

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 <b_new.

数据结构不需要支持删除.

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：速度可以很容易地提高：a）一旦找到较年轻的元素，您可以从该点继续寻找较旧的元素，而不是再次迭代，b）而不是使用List的Sort方法对其进行排序，您可以使用 InsertAt(0 或第一个长辈的索引)