using System;


namespace MinABS
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 100;
            int[] a = new int[n];
            Random rand = new Random();
            int min = int.MaxValue;
            int max = int.MinValue;
            Console.WriteLine("产生了" + n + "个数据的实验数组,");
            Console.WriteLine("本程序适用于int.MinValue到int.MaxValue范围，请自行修改输入的量和范围");
            for (int i = 0; i < n; i++)
            {
                //赋值并且取到最大最小值
                //a[i] = rand.Next(int.MinValue, int.MaxValue);
                 a[i] = rand.Next(-100, 100);
                if (a[i] < min) { min = a[i]; }
                if (a[i] > max) { max = a[i]; }
                 Console.Write(a[i] + " ");                
            }
             Console.WriteLine();
            Console.WriteLine("在O(n)内得到最大最小分别是：");
            Console.WriteLine(max + "和" + min);
            
            long offset = (long)max + Math.Abs((long)min);
            //规划数组的长度。每个byte有8位长
            int len = (int)(offset >> 3) +1 ;
            Byte[] B = new Byte[len];
            int kkkk = 0;
            bool IsSame = false;//是否有重合点标记
           
            //O(n)的时间内分配到了Byte[]中。
            
            for (int i = 0; i < n; i++)
            {
                offset = (long)a[i] - (long)min;
                int index = (int)(offset >> 3);
                int temp = B[index];
                //把末k位变成1
                //把右数第k位变成1 例如：(00101001->00101101,k=3)     x | (1 << (k-1))
             
                int tempOffSet = (1 << (  (int)(offset & 7) ) );
                //判断重合
                if (!IsSame)
                {
                    kkkk = temp & tempOffSet;
                    if ((temp & tempOffSet) >= 1)
                    {
                        IsSame = true;
                        //如果0算最小距离就在这里退出吧。本代码判断重合，但没把0作为结果。                        
                    }
                }
                int bbb = B[index];                
                B[index]  |=  (Byte)(tempOffSet);          
                int aaa = B[index];
  
            }
            //最小距离初始为最大。

            Console.WriteLine("在O(n)的时间内分配到了Byte[]中，正在计算最小距离，请稍候。。。。。");

            long minABS = long.MaxValue;
            long lastIndex = -1;

            //在常数范围内循环，复杂度不增加。最坏的情况是32*int.MaxValue次。

            for (int i = 0; i < B.Length; i++)
            {
                //if (B[i] == 0) { continue; }
                //在常数范围内循环，复杂度不增加。
                for (int k = 0; k < 8; k++)
                {
                    if (((B[i] >> k) & 1) == 1)
                    {
                        if (lastIndex >= 0)
                        {
                            long temp = ((long)i << 3) + k - lastIndex;
                            if (temp < minABS)
                            {
                                minABS = temp;
                               Console.WriteLine("目前得到了最小距离：" + minABS);
                            }
                        }
                        lastIndex = (i << 3) + k;                        
                    }
                }
            }
            if (IsSame)
            { Console.WriteLine("有重合点"); }
            else
            { Console.WriteLine("无重合点"); }

            Console.WriteLine("不考虑重合最小距离是：" + minABS);
            Console.WriteLine("总复杂度是：O(n)");