十叉树之关于怎么在10万个手机号码中选择重复号码的问题。

《甩葱歌》怀旧版，始于1974（附多个不同版本）

几道有意思的逻辑分析题

Jul 21

tommyhu , 22:36 , ASP.NET , Comments(1) , Trackbacks(0) , Reads(8087) , Via Original

Large | Medium | Small

十叉树之关于怎么在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];
        }

}
}

▲返回顶部