TOMMYHU

十叉树之关于怎么在10万个手机号码中选择重复号码的问题。
大家一般都认为用Hash的办法。不过其实还有更高效的算法。

计算机图形学中，有个八叉树量化法，是用来从24颜色中查找重复颜色，并且进行计数归并的算法。它的算法思想是八叉树一共8层，每层都有8个节点，每一条路径从根到页正好对应8个位.
而颜色RGB  三个数字正好可以拼成一个由0-7数字组成的8位数字，于是正好可以用八叉树算法进行插入。

八叉树比较复杂，不过对于我们的这个需求来说，其实比较简单。
我们这个算法是10叉树，每层都保存了0-9   10个数字。层数就是手机号码的长度。
手机号的第一位就是第一层，只需遍历到最后一层即可判断是否重复。
于是让我们来实现这个十叉树。效率都和回复中的Linq做比较。
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 {     unsafe class Program     {         static void Main(string[] args)         {             //示例数组，存放手机号             string[] mobileArray = new string[100000];// { "13900001234", "13900001235", "13900001236", "13900001237", "13900001234" };             for (int i = 0; i < 100000; i++)             {                 mobileArray[i] = "1390000"                     + (i.ToString().Length > 4 ? i.ToString().Substring(0, 4) : (i.ToString() + "0000").Substring(0, 4));             }             ////linq语句来实现【select mobile from tmpTable group by mobile having count(*)>1】的效果             var selMobile = from n in mobileArray group n by n into g where g.Count() > 1 select g.Distinct();// select g;             System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();             sw.Reset();             sw.Start();             int count1 = 0;             //通过两层循环输出重复的手机号             foreach (var mobile in selMobile)             {                 foreach (string multiMobile in mobile)                 {                     count1++;                     //Console.WriteLine(multiMobile);                 }             }             sw.Stop();             Console.WriteLine("Linq共有重复号" + count1+"耗时"+ sw.ElapsedTicks );             TenNodeTree tree = new TenNodeTree();             TenNodeTree tree2 = new TenNodeTree();             sw.Reset();             sw.Start();             int count2 = 0;             //mobileArray = new string[] { "13900001234", "13900001235", "13900001236", "13900001237", "13900001234", "13900001236" };             foreach (var item in mobileArray)             {                 fixed (char* no = item)                 {                     if (!tree.Add(no , 11 ))                     {                         if (tree2.Add(no,11))                         {                             count2++;                         }                     }                 }             }             sw.Stop();             Console.WriteLine("十叉树共有重复号" + count1 + "耗时" + sw.ElapsedTicks);             Console.ReadLine();         }         class TenNodeTree         {             public TenNode Root = new TenNode();             public bool Add(char* no,int len)             {                 TenNode cnode = Root;                 bool isadd = false ;                 for (int i = 0; i < len; i++)                 {                     char k = *no;                     if (cnode.Child[k-48] == null)                     {                         isadd = true;                         cnode.Child[k-48] = new TenNode();                     }                     cnode = cnode.Child[k-48];                     no++;                 }                 return isadd;             }         }         class TenNode         {             public TenNode[] Child = new TenNode[10];         }     } }