首页 > 代码库 > 关于遗漏的一种算法
关于遗漏的一种算法
玩过高频彩票的人知道，开奖号码下方会有该号码的遗漏情况。当然，大乐透和双色球也有遗漏数据。
下面以我接触比较多的泳坛夺金展开，以其50万期开奖结果为例（事实上百度能找到的是2002年开始制定的游戏规则，到目前为止大约50万期，文中这50万期数据是我伪造的）。
泳坛夺金每期开出4个号码，每个号码的取值在1-8之间。详情参考百度。
之前看过一同事写的号码遗漏算法，逻辑就不说了，因为那代码我无心去看，执行了一下，耗时惨不忍睹。
后来采用一次计算，xml文件+memcached并用来解决。
最近在熟悉vs2017，就用这个来写写看。
写完之后测试，50万条数据计算最大遗漏耗时约300ms，算法的时间复杂度o(n)。
1 /// <summary> 2 /// 计算最大遗漏 3 /// </summary> 4 public class CalculateMaxMiss 5 { 6 /// <summary> 7 /// 开奖结果集合，index表示row number,v表示开奖结果集合 8 /// </summary> 9 private static List<(int index, int[]v)> objs;10 11 static CalculateMaxMiss()12 {13 //Datas.Results类型为IList<string>，表示开奖结果列表，不拆分14 objs = Datas.Results.Select(p => p.Split(‘,‘).Select(int.Parse).ToArray()).Select((p, index) => (index, p)).ToList();15 }16 /// <summary>17 /// 计算位置n出现号码m的最大遗漏18 /// </summary>19 /// <param name="position">位置</param>20 /// <param name="number">号码</param>21 /// <returns></returns>22 private static (int position, int number, int maxMiss) Calculate(int position,int number)23 {24 var arr = objs.Where(p => p.v[position-1] == number).Select(p => p.index).ToList();25 int max = 0;26 for (int i =1; i < arr.Count; i++)27 {28 int minus = arr[i] - arr[i-1];29 max = max > minus ? max : minus;30 }31 return (position, number, max);32 }33 /// <summary>34 /// 计算所有数据号码遗漏35 /// </summary>36 /// <returns></returns>37 public static IList<(int position, int number, int maxMiss)> Calculate()38 {39 List< (int position, int num, int times) > r=new List<(int position, int num, int times)>();40 for (int position = 1; position < 5; position++)41 {42 for (int number = 1; number < 9; number++)43 {44 r.Add(Calculate(position,number));45 }46 }47 return r;48 }49 }
事实上，之前同事写的算法计算的数据并没有50万，大约在10万左右
测试数据在下面
测试用481开奖结果.zip
关于遗漏的一种算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。