日期:2014-05-18  浏览次数:20708 次

求1数据结构,给定一个时间值,在时间范围内快速查找,求方法,思路


一个子项,有开始时间,有结束时间,单独子项时间不重叠, 给定一个 时间,如何快速 查到该项? 

示例(时间用double):

C# code


class 日常活动{

      double 开始时间; 
      double 结束时间;
      string 活动记录;

}


class 个人记录{
   日常活动[] 我的记录A; 
  
   public string 活动记录A在时间点(double 随机输入时间){}        // 这里有没有高效的(非遍历)方法?
}




一直用遍历,

求更好的实现方法

什么都能改,可以用别的数据结构,可以预处理,只求高效




------解决方案--------------------
排序,然后用2分找,或者按日期分段建索引
------解决方案--------------------
用Linq+字典。
------解决方案--------------------
单项不重叠就好办了。

注意以下例子中的
BinarySearch: 二分查找,复杂度log(N)。
orderby:排序了才能二分查找。
IComparable:可比较才能排序。
C# code

class Program
{
    static void Main(string[] args)
    {
        个人记录 records = new 个人记录(new 日常活动[]
            {
                new 日常活动(){开始时间 = 7,   结束时间 = 7.5, 活动记录 = "早餐"},
                new 日常活动(){开始时间 = 9.0, 结束时间 = 11,  活动记录 = "客户会议"},
                new 日常活动(){开始时间 = 12,  结束时间 = 13,  活动记录 = "午餐"},
                new 日常活动(){开始时间 = 14,  结束时间 = 18,  活动记录 = "娱乐"},
            }
        );
        string 记录0 = records.活动记录在时间点(8);    // null
        string 记录1 = records.活动记录在时间点(12.5); // 午餐
        string 记录2 = records.活动记录在时间点(14);   // 娱乐
        string 记录4 = records.活动记录在时间点(20);   // null
    }
}

class 日常活动 : IComparable<日常活动>
{
    public double 开始时间;
    public double 结束时间;
    public string 活动记录;
    public int CompareTo(日常活动 other)
    {
        if (this.开始时间 < other.开始时间) return -1;
        if (this.开始时间 > other.开始时间) return +1;
        return 0;
    }
}
class 个人记录
{
    日常活动[] 我的记录A;
    public 个人记录(IEnumerable<日常活动> 活动记录)
    {
        this.我的记录A = 活动记录.OrderBy(r => r.开始时间).ToArray();
    }
    public string 活动记录在时间点(double 时间点)
    {
        int hit = Array.BinarySearch<日常活动>(this.我的记录A, new 日常活动() { 开始时间 = 时间点 });
        if (hit < 0) hit = (~hit) - 1;
        if (hit >= 0 && 我的记录A[hit].开始时间 <= 时间点 && 时间点 <= 我的记录A[hit].结束时间) return 我的记录A[hit].活动记录;
        return null;
    }
}

------解决方案--------------------
既然有开始和结束时间,也保证了时间项不重复,二分查找应该算比较快的,