1 using System.Linq; 2 using System; 3 namespace ConsoleApplication3 4 { 5     class Program 6     { 7         static void Main(string[] args) 8         { 9             int[] intergers = { 11, 8,9, 6, 12, 7, 5, 10, 14,13, 8 };  //[5,14],多一个810             Console.WriteLine(GetRepeatOrLack(intergers));11             Console.ReadKey();12         }13         //给定n-m+2(或n-m)个正整数组成的乱序序列，其元素是m到n中的不同的整数，并有且只有一个是重复(或缺失)的。该算法返回那个数14         private static int GetRepeatOrLack(int[] arrInts)15         {16             int temp = 0;17             int upper = arrInts.Length;18             //temp为数组arrInts中的所有数的异或结果19             for (int i = 0; i < upper; i++)20             {21                 temp = temp ^ arrInts[i];22             }23             return temp ^ GetXor(arrInts.Min(), arrInts.Max()+1);24         }25         /// <summary>26         /// 返回从start到end的连续若干个整数的异或结果27         /// </summary>28         /// <param name="start">开始位置（包含）</param>29         /// <param name="end">结束位置（不包含）</param>30         /// <returns>[start,end-1]闭区间异或结果</returns>31         private static int GetXor(int start, int end)32         {33             if (start>=end)34             {35                 throw new ArgumentException("end必须大于start");36             }37             if (start + 1 == end)38             {39                 return 0;40             }41             return GetXorFrom1ToN(start) ^ GetXorFrom1ToN(end);42         }43         /// <summary>44         /// 返回从1到end的连续若干个整数的异或结果45         /// </summary>46         /// <param name="end">结束位置（不包含）</param>47         /// <returns>[1，end-1]闭区间的异或结果</returns>48         private static int GetXorFrom1ToN(int end)49         {50             if (end<=1)51             {52                 throw new ArgumentException("参数end须大于等于2");53             }54             if (2== end)55             {56                 return 0;57             }58             int mod = (end - 1) % 4;59             switch (mod)60             {61                 case 0:62                     return end - 1;63                 case 1:64                     return 1;65                 case 2:66                     return end;67                 case 3:68                     return 0;69                 default:70                     return 0;71             }72         }73 74         # region [1,n]闭区间的连续正整数的异或结果是有规律75         //我们发现了[1,n]闭区间的连续正整数的异或结果是有规律的，即:76         //          余数  [1,n]的异或结果Xor77         //           0    n78         //           1    179         //n mod 4 =  2    n+180         //           3    081         //所以下面的方法可以改造成上面的样子82         //private static int GetXor(int start, int end)83         //{84         //    int result = 0;85         //    if (start + 1 == end)86         //    {87         //        return 0;88         //    }89         //    for (int i = start; i < end; i++)90         //    {91         //        result = result ^ i;92         //    }93         //    return result;94         //}95         #endregion96         97     }98 }