算法学习--数组
一个数组存放了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;
}
