首页 > 试题广场 >

寻找奇数

[编程题]寻找奇数

热度指数：8974 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

现在有一个长度为 n 的正整数序列，其中只有一种数值出现了奇数次，其他数值均出现偶数次，请你找出那个出现奇数次的数值。

数据范围： $1 \le n \le 2 \times 10^6 \$

输入描述:

第一行：一个整数n，表示序列的长度。第二行：n个正整数ai，两个数中间以空格隔开。

输出描述:

一个数，即在序列中唯一出现奇数次的数值。

示例1

输入

5
2 1 2 3 1

输出

示例2

输入

1
1

输出

算法知识视频讲解

Chrety

XOR的简单应用

#include <bits/stdc++.h>
using namespace std;
int n, x, ans;
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        ans ^= x;
    }
    cout << ans;
}

编辑于 2019-07-20 08:05:38 回复(0)

Polestar_a

py异或有点慢

n = int(input())
res = list(map(int, input().split()))
num = 0
for i in res:
    num = num^i
print(num)

发表于 2019-08-09 23:13:10 回复(5)

moon-star

//运行时间：211ms
//占用内存：612k
#include <iostream>
using namespace std;

int main()
{
    int n = 0;
    int num;
    unsigned int sum = 0;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> num;
        sum ^= num;
    }
    cout << sum;
    return 0;
}

编辑于 2019-08-01 13:24:55 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,x,s=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        s ^= x;
    }
    cout<<s<<endl;
    return 0;
}

发表于 2019-09-09 00:19:50 回复(1)

pein531

任何数与0异或都等于它本身，与自己异或都为0，因此对整个数组按顺序进行异或之后，出现偶数次的数全为0，异或的最终结果就是出现奇数次的那个数

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strN;
        while((strN = br.readLine()) != null) {
            String[] strArr = br.readLine().split(" ");
            int remain = 0;
            for(int i = 0; i < strArr.length; i++)
                // 出现偶数次的数在经过不断异或后一定为0,与0异或不改变数
                remain ^= Integer.parseInt(strArr[i]);
            // 所以最后剩下的数就是出现过奇数次的数
            System.out.println(remain);
        }
    }
}

发表于 2020-10-27 20:30:48 回复(0)

牛客116675081号

解题思路：这道题采用异或方法，因为相同的两个数进行异或结果为0,然后再拿0跟其他数进行异或，结果是那个数，就能找出奇数个的数了

#include<stdio.h>
int main()
{
    int n=0;
    int num=0;
    int sum=0;
    scanf("%d",&n);
    
    for(int i=0;i<n;i++)
    {
        scanf("%d",&num);
        sum^=num;
    }
    
    printf("%d\n",sum);
    return 0;
}

发表于 2022-03-09 16:24:28 回复(0)

202308764547周军

异或：二进制比特位相同则0，不同则1.两个相同的数字异或得到的是0，基于这个思路，这道题对数组中的所有数据进行逐一异或就可以解决得到奇数次的数字，因为偶数次的数字都被异或成为0了，最后单独保留了奇数次的数字。

#include <stdio.h>
int main()
{
int n;
while(~scanf("%d", &n)) {
int num = 0, tmp = 0;
//对每个数字进行异或，出现偶数次的就会异或为0了，而奇数次刚好剩下的就是对应数字
for (int i = 0; i < n; i++) {
scanf("%d", &tmp);
num ^= tmp;
}
printf("%d\n", num);
} 
return 0;
}

发表于 2024-10-20 14:37:09 回复(0)

Python3

TS9527

两种解法：

1. 用一个集合作为出现过的数的记录。遍历数组，如果这个数出现过，就把它从集合里移除，否则加入。最后集合会剩一个元素，那就是答案。

class MainActivity:

    def main(self):
        # Read the data
        n = int(input())
        nums = list(map(int, filter(lambda x: len(x) > 0, input().split(' '))))
        # Initialization
        records = set()
        # Traverse
        for num in nums:
            if num in records:
                records.remove(num)
            else:
                records.add(num)
        print(list(records)[0])


if __name__ == '__main__':
    M = MainActivity()
    M.main()

2. 用异或计算。出现偶数次的数字异或完后为0，奇数次的会留下。

class MainActivity:

    def main(self):
        # Read the data
        n = int(input())
        nums = list(map(int, filter(lambda x: len(x) > 0, input().split(' '))))
        # Initialization
        result = 0
        # Traverse
        for num in nums:
            result ^= num
        print(result)


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-08-24 14:19:32 回复(0)

老秦刷题

暴力求解

#include <stdio.h>

#include<stdlib.h>

int cmp(const void* e1, const void* e2)

{

return *(int*)e1 - *(int*)e2;

}

int main() {

int a = 0;

scanf("%d", &a);

int arr[2000000] = { 0 };

int i = 0;

for (i = 0; i < a; i++)

{

scanf("%d", &arr[i]);

}

//排序

qsort(arr, a, sizeof(int), cmp);

int count = 1;

for (i = 0; i < a; i++)

{

if (arr[i] == arr[i + 1])

{

count++;

continue;

}

if (count % 2)

{

printf("%d", arr[i]);

return 0;

}

count = 1;

}

return 0;

}

发表于 2023-09-13 11:09:28 回复(0)

水月梦镜花

#include <stdio.h>

#include <stdlib.h>

int main()

{

int n = 0;

scanf("%d", &n);

int* arr = (int*)malloc(sizeof(int) * n);

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

{

scanf("%d", &arr[i]);

}

int ans = 0;

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

{

ans ^= arr[i];

}

printf("%d", ans);

free(arr);

return 0;

}

发表于 2023-08-24 21:44:22 回复(0)

LMY.1

C语言

#include <stdio.h>

int main()
{
    int n = 0;
    scanf("%d", &n);
    int num = 0;
    int temp = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &temp);
        num = num ^ temp;
    }
    printf("%d", num);
    return 0;
}

发表于 2023-01-31 17:20:00 回复(0)

宇宇宇💤💤💤

这个题明明使用哈希表是很容易的，但它就不告诉我数据的范围。

发表于 2023-01-29 22:08:08 回复(0)

semi_

#include <stdio.h>
#include<stdlib.h>
int main() {
    int n=0;
    int num=0;
    scanf("%d",&n);
    int* arr=(int*)malloc(sizeof(arr)*n);
    int i=0;
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
        num^=arr[i];
    }
    printf("%d\n",num);
    free(arr);
    arr=NULL;
    return 0;
}

发表于 2023-01-26 15:21:43 回复(0)

牛客646557201号

这道题只需要知道

(a^b)^a == b

发表于 2022-08-30 12:04:34 回复(0)

新的一天，啦啦啦

中心思想：使用位运算——异或

n = input()
alist = list(map(int, input().split()))

err = 0
# 位运算中的异或运算
for item in alist:
    err = err ^ item
    
print(err)

发表于 2022-08-02 22:32:54 回复(0)

一个fw狗

#include<stdio.h>
int main()
{
    int n,i;
    scanf("%d",&n);
    int count,m=0;
    for(i=0;i<n;i++)
    {
        scanf("%d",&count);
        m^=count;
    }
    printf("%d",m);
    return 0;
}

发表于 2022-02-21 16:52:48 回复(0)

阿金要努力

#include<stdio.h>
int main()
{
    int n=0,m=0;
    int ret=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&m);
        ret^=m;
    }
    printf("%d\n",ret);
    return 0;
}

发表于 2022-02-02 18:43:59 回复(0)

星燧贸迁

#include<stdio.h>

int main()
{
    long long n=0;
    scanf("%ld",&n);
    long long x=0;
    long long max=0;
    while(~scanf("%ld",&x))
    {
        max^=x;
    }
    printf("%ld\n",max);
    return 0;
}

发表于 2022-01-26 22:39:14 回复(0)

C/C++

louis_ncu

//这玩意儿是看运气的，我运行了3次，前两次超时了，第三次通过了，f*ck!!!
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <stack>
#include <unordered_map>
#include <map>
#include <queue>

using namespace std;

void findTheNumberAppearOnlyOnce() {
    int n, x, res = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        res ^= x;
    }
    cout << res << endl;
}

int main(){
    findTheNumberAppearOnlyOnce();
    return 0;
}

发表于 2020-05-24 22:23:57 回复(0)

Python

Freedom2020

n = int(input().strip())
array = list( map(int, input().strip().split()) )
ans = 0
for a in array:
    ans ^= a
print(ans)

XOR算法。

a^b：按位异或运算，即当二进制位相同时结果为0，反之为1。例如1^2 =3，（01）^（10）=（11）。异或运算可以过滤掉成双成对的数字，剩下那个“孤独”的单身数。

发表于 2020-05-07 02:14:11 回复(0)

提交观点

问题信息

快手穷举算法工程师 2019 查找数学

上传者：小小

难度：

28条回答 54收藏 9471浏览

通过挑战的用户

查看代码

牛客65043...

2022-10-27 10:19:17
offer快点...

2022-09-15 22:21:31
Choose＆...

2022-09-15 18:13:31
牛客55837...

2022-09-15 17:52:25
牛客54485...

2022-09-15 11:01:10

寻找奇数

输入描述:

输出描述:

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题