查找数组中的唯一元素

问题

例如给定一个数组有101个元素，其实50个元素出现再次，只有一个仅出现一次，写一个函数找出该唯一的元素，元素均为整型。

1. 最差的方法

前提是元素都大于0.

int findOdd(int *input, int len) {
	int i, j, z, *buff, blen = (int) (len / 2 + 1);

	buff = (int *) malloc(sizeof(int) * blen);
	
	for (i = 0; i < len; i++) {
		z = -1;
		for(j = 0; j < blen; j++) {
			if (buff[j] == 0) {
				if (z == -1) {
					z = j;
				}
				continue;
			}
			if (buff[j] == input[i]) {
				buff[j] = 0;
				z = -1;
				break;
			}
		}
				
		if (z >= 0) {
			buff[z] = input[i];
		}

	}

	j = 0;
	
	for (i = 0; i < blen; i++) {
		if (buff[i] != 0) {
			j = buff[i];
			break;
		}
	}

	free(buff);
	return j;
}

2. 好点的方法

使用stdlib的快速排序.

int compare (const void * a, const void * b) {
	return ( *(int*)a - *(int*)b );
}

int findOdd2(int *input, int len) {
	int i = 0;
	
	qsort(input, len, sizeof(int), compare);	

	while (i < len) {
		if (input[i] != input[i+1]) {
			break;
		}
		i = i + 2;
	}
	return input[i];
}

3. 最佳的算法

不知道，请您指点。