两个月前做过提交了 7遍都超时了。这次回去再试试看，结果还提交了两次错误答案。最后回归超时。
Create a timebased key-value store class TimeMap, that supports two operations.
创造一个类TimeMap 用来基于时间的键值对，并且构建两个方法
1. set(string key, string value, int timestamp)
Stores the key and value, along with the given timestamp.
Set赋值，存储key, value, timestamp 时间戳
2. get(string key, int timestamp)
Get 取值，根据key和时间戳timestamp
Returns a value such that set(key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp.
If there are multiple such values, it returns the one with the largest timestamp_prev.
If there are no values, it returns the empty string ("").
返回<=这个时间戳的值，如果有多个时间戳满足条件，则选择最大的那个时间戳时候的值，如果没有结果返回“”
public class TimeMap {
private Dictionary<string, Dictionary<int, string>> keysDt;
/** Initialize your data structure here. */
public TimeMap()
{
keysDt = new Dictionary<string, Dictionary<int, string>>();
}
public void Set(string key, string value, int timestamp)
{
var history = new Dictionary<int, string>();
if (keysDt.ContainsKey(key))
{
history = keysDt[key];
history.Add(timestamp, value);
keysDt[key] = history;
}
else
{
history.Add(timestamp, value);
keysDt.Add(key, history);
}
}
public string Get(string key, int timestamp)
{
string res = "";
if (keysDt.ContainsKey(key))
{
Dictionary<int, string> history = keysDt[key];
if (history.ContainsKey(timestamp)) return history[timestamp];
var allKeys = history.Keys.Where(x => x <= timestamp).OrderByDescending(x => x);
if (allKeys.Count() == 0)
{
return "";
}
else
{
return history[allKeys.FirstOrDefault()];
}
}
return res;
}
}
看了其他C#的答案 这个linq查询的也超时了
我自己的二分查找也超时了。
public string Get(string key, int timestamp)
{
string res = "";
if (keysDt.ContainsKey(key))
{
Dictionary<int, string> history = keysDt[key];
if (history.ContainsKey(timestamp)) return history[timestamp];
int[] times = new int[history.Count];
int i = 0;
foreach (int k in history.Keys)
{
times[i] = k;
i++;
}
Array.Sort(times);
int start = 0;
int end = times.Length - 1;
while (start + 1 < end)
{
if (times[start + (end - start) / 2] < timestamp)
{
start = start + (end - start) / 2;
}
else
{
end = start + (end - start) / 2;
}
}
if (timestamp >= times[end]) res = history[times[end]];
else if (timestamp < times[start]) res = "";
else res = history[times[start]];
}
return res;
}
额的神呀 两个月以后并没有灵光乍现。 有没有大神帮我想想 是不是C#就没有好的数据结构能搞定了。