算法学习--数组
一个数组存放了2n+1个整数,其中有n个数出现了2次,1个数出现了1次,找出出现1次的数是多少? //方法一:借助辅助数组(长度为n+1,元素为一结构体(包含数值和 //个数两个成员))进行计数,但是时间复杂度为O(n*n),空间复杂度为O(n+1) //本来是想把Val定义为结构体的,但由于结构体是值类型,不是引用类型, //添加到List结合中的元素的属性值不能被修改,把List中的一个元素赋给另一个Val,修改Val中的value和num, //List中对应的Val相关的属性值是不会改变的,因为他们是内存中的两个不同单元 //总之:谁叫我C学得不好,用的是C#呢,不然就用C实现了。 public class Val {public int value;//值 public int num;//出现的次数 }public int FindA(int[] A, int n) { List<Val> list = new List<Val>(); Val val ; int j=0;for (int i = 0; i < n ; i++) {while (j < n) {bool isExist = false;for(int k=0;k<list.Count;k++) { if (list[k].value == A[j]) { isExist = true; list[k].num = 2;break; } }if (!isExist) { val = new Val(); val.value = A[j]; val.num = 1; list.Add(val); } j++; } }int result = -1;foreach (Val v in list) {if (v.num == 1) { result = v.value;break; } }return result; }//方法二:借助一个长度为n/2+1的数组B,如果A中的元素不在B中,就存入B中,//如果在B中,存在的那个元素后面所有的元素向前移一个单位,相当于去掉这个在B中存在的元素,//这一进一出的,出现偶数次的都去掉了,只剩下出现奇数次的元素。 public int FindI(int[] A, int n) {int[] B = new int[n / 2 + 1];int k = 0;for (int i = 0; i < n; i++) {bool isExist = false;for (int j = 0; j <= k; j++) {if (A[i] == B[j]) { isExist = true;for (int f = j; f < k - 1; f++) { B[f] = B[f + 1]; } k--;break; } }if (!isExist) { B[k] = A[i]; k++; } }return B[0]; }//方法三:排序。相等的数当然就在一起,单独的那个数就是那个只出现一次的了,哈哈... public int FindS(int[] A, int n) {for (int i = 0; i < n - 1; i++) {for (int j = i + 1; j < n; j++) {if (A[i] > A[j]) {int temp = A[j]; A[j] = A[i]; A[i] = temp; } } }int result = -1;for (int i = 0; i < n; i = i + 2) {if (A[i] != A[i + 1]) { result = A[i];break; } }return result; }//方法四:异或运算(博客园这位帅哥牛) //异或运算 0与任何数异或等于任何数,相等的两个数异或等于0,//也就是两个数对应的二进制位进行异或运算;0^0=0 , 1^0=1 , 0^1=1 , 1^1=0//出现偶数次都完蛋了,就剩下出现奇数次的了 public int FindSpecial(int[] A, int n) {int res = 0;for (int i = 0; i < n; i++) { res = res ^ A[i]; }return res; } 本文转自啊汉博客园博客,原文链接:http://www.cnblogs.com/hlxs/archive/2010/11/16/2087989.html