传说中百度的试题,用C#做二进制运算得到2.5亿数字中不重复数字数的O(n)算法

本文主要是介绍传说中百度的试题,用C#做二进制运算得到2.5亿数字中不重复数字数的O(n)算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

using System;
using System.IO;
using System.Collections;

namespace bucketSort
{
    class Program
    {
        public const int maxCount = 25 * 1000 * 10000;//2.5亿不算大，还没超过整数范围呢
        public const string FileName = @"c:/test.txt";

        public static void Main(string[] args)
        {

            //写文件，用来实验的；写一遍就可以了；
            //writeFile();
            //Console.ReadLine();
            //return;

            FileStream FileReader = new FileStream(FileName, FileMode.Open);

            //循环读入全部正个整数，每次读1个整数，产生1个bit,读到结尾标记就不读了；

            int index = 0;
            //创建两个够长的BitArray
            //发现了.NET一个Bug,就是BitArray并不是可以按照int.MaxValue构造,所以限制了一下数字范围，期待微软能修改这个Bug。
            //即使是在最大整数范围内，-2,147,483,648 到 2,147,483,647是4亿个Bit,1亿多字节， New这两个容器应该是2个100多M,在600M范围内。
            //一个数组表示有没有这个数字

            BitArray CountorSingle = new BitArray(250000000 + 1);

            //第二个数组表示是否多次出现这个数字
            BitArray CountorMore = new BitArray(250000000 + 1);

            //循环检测，复杂度是O(N)
            while (true)
            {
                byte[] tempByte = new byte[4];
                index += FileReader.Read(tempByte, 0, 4);
                int tempInt = System.BitConverter.ToInt32(tempByte, 0);

                if (tempInt == -1)
                {
                    break;
                }
                else
                {
                    if (CountorSingle.Get(tempInt))
                    {
                        //出现多次,设置这个值，复杂度是O(1)
                        CountorMore.Set(tempInt, true);
                    }
                    else
                    {
                        ////出现一次,设置这个值，复杂度是O(1)
                        CountorSingle.Set(tempInt, true);
                    }
                }
            }
            FileReader.Close();

            //从CountorSingle中排除CountorMore，采用逻辑Xor运算，复杂度是O(n)
            //Xor运算如果两者值相同，为False,1,0=1 ; 0,1=1 ; 1,1=0 ; 0,0=0 前边已经排除了0,1的可能性。
            CountorSingle = CountorSingle.Xor(CountorMore);//复杂度是O(n)
            //再读负数那个文件。

            //关键时刻到来了
            int sum = 0;

            //复杂度是O(n)
            foreach (bool isExists in CountorSingle)
            {
                if (isExists)
                {
                    sum++;
                }
            }

            Console.WriteLine("全部计算复杂度是O(n)，结果是：" + sum);
            Console.ReadLine();
            //几分钟后，看到屏幕上显示：全部计算复杂度是O(n)，结果是：91836109

        }
        public static long getIndex(int x)
        {
            //int.MinValue的下标位于0，负整数n的下标是0-(long)int.MinValue；
            //0的下标位于1-(long)int.MinValue,正整数n的下标是n+1-(long)int.MinValue；
            if (x >= 0)
            {
                return (x + 1 - (long)int.MinValue) / 4;
            }
            else
            {
                return (0 - x) / 4;
            }
        }
        public static void writeFile()
        {
            //写文件，用来实验的；写一遍就可以了，正数和零写到正数文件里，负数写到负数文件里。
            //写2个文件是因为.NET的BitArray类只有构造函数是int的，如果都写一起，那么就超出了处理范围。

            FileStream FileWriter = new FileStream(FileName, FileMode.OpenOrCreate);

            System.Random rand = new Random();
            int i = 0;
            for (; i < maxCount; i++)
            {
                //写入2.5亿个整数，一个整数是4个Byte[],随机在250000000范围内；
                //发现了.NET一个Bug,就是BitArray并不是可以按照int.MaxValue构造。
                //所以就只好限制在250000000内了，先只考虑正数和0，
                //负数可以另外改一下，放另外文件里计算。
                int tempInt = rand.Next(0, 250000000);
                FileWriter.Write(System.BitConverter.GetBytes(tempInt), 0, 4);

            }
            //结尾写一个-1做标记。
            FileWriter.Write(System.BitConverter.GetBytes(-1), 0, 4);
            FileWriter.Close();
           //靠，970多兆的文件。实验完赶紧删除。
            Console.WriteLine("写文件完毕！");
        }

    }
}