给定一个含有n个元素的整型数组array，其中只有一个元素出现奇数次，找出这个元素。
思路分析：
这道题一般人的第一反应都是遍历数组，将数组中每个元素出现的次数保存下来，然后遍历这些次数，返回奇数者。时间复杂度O(n2），累不累啊。因为对于任意一个数k，有k^k=0，k^0=k，所以将array中所有元素进行异或，那么个数为偶数的元素异或后都变成了0，只留下了个数为奇数的那个元素。酱紫的话时间复杂度只有O(n)，多省事啊。
程序示例如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 |
#include "stdafx.h"#include <stdio.h>int FindElementWithOddCount(int* a, int
n){ int
r = a[0]; for
(int i = 1; i < n; ++i) { r ^= a[i]; } return
r;}int
main(){ int
array[] = { 1, 2, 2, 3, 3, 4, 1 }; int
len = sizeof(array) / sizeof(array[0]); printf("%d\n", FindElementWithOddCount(array, len)); getchar(); return
0;} |
效果如图：
如何找出数组中出现奇数次的元素,布布扣,bubuko.com
原文：http://www.cnblogs.com/cysolo/p/3590896.html