题解 | 寻找奇数

解题思路

为了找到在序列中唯一出现奇数次的数值，我们可以利用异或运算的特性。具体步骤如下：

异或运算特性：

对于任何数 x，有 x ^ x = 0，即相同的数异或结果为 0。

对于任何数 x，有 x ^ 0 = x，即任何数与 0 异或结果为其本身。

因此，若一个数在序列中出现奇数次，其他数出现偶数次，最终的异或结果将是那个出现奇数次的数。

遍历序列：

初始化一个变量 result 为 0，遍历整个序列，将每个数与 result 进行异或运算。

输出结果：

遍历结束后，result 中存储的就是出现奇数次的数值。

代码

cpp

java

python

#include

#include

using namespace std;

class Solution {

public:

int findOddOccurrence(int n, vector& arr) {

int result = 0;

for (int num : arr) {

result ^= num; // 进行异或运算

}

return result; // 返回出现奇数次的数值

}

};

int main() {

Solution solution;

int n;

cin >> n; // 读取序列长度

vector arr(n);

for (int i = 0; i < n; i++) {

cin >> arr[i]; // 读取序列

}

cout << solution.findOddOccurrence(n, arr) << endl; // 输出出现奇数次的数值

return 0;

}

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class Main {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* @param n 序列的长度

* @param arr 序列的整数数组

* @return int 出现奇数次的数值

*/

public int findOddOccurrence(int n, int[] arr) {

int result = 0;

for (int num : arr) {

result ^= num; // 进行异或运算

}

return result; // 返回出现奇数次的数值

}

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int n = Integer.parseInt(br.readLine()); // 读取序列长度

int[] arr = new int[n];

String[] input = br.readLine().split(" "); // 读取序列并分割

for (int i = 0; i < n; i++) {

arr[i] = Integer.parseInt(input[i]); // 将字符串转换为整数

}

Main solution = new Main();

System.out.println(solution.findOddOccurrence(n, arr)); // 输出出现奇数次的数值

}

}

def find_odd_occurrence(n, arr):

result = 0

for num in arr:

result ^= num # 进行异或运算

return result # 返回出现奇数次的数值

# 示例用法

if __name__ == "__main__":

n = int(input()) # 读取序列长度

arr = list(map(int, input().split())) # 读取序列

print(find_odd_occurrence(n, arr)) # 输出出现奇数次的数值

算法及复杂度

算法：异或运算

时间复杂度：，其中 是序列的长度

空间复杂度：，只使用了常数级的额外空间