首页 > 试题广场 >

寻找奇数

[编程题]寻找奇数

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

现在有一个长度为 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)

老秦刷题

暴力求解

#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)

Josepy

// 40%超时了

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args)  throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] str = br.readLine().split(" ");
        Map<String, Integer> map = new HashMap();
        for(int i = 0; i < n; i++){
            if(!map.containsKey(str[i])){
                map.put(str[i], 1);
            }else{
                map.put(str[i], map.get(str[i])+1);
            }
        }
        for(String key:map.keySet()){
            if(map.get(key)%2!=0){
                System.out.println(key);
                return;
            }
        }
    }
}

发表于 2020-04-21 23:40:17 回复(0)

Python

黄沙遮天

n=int(input())
m=list(map(int,input().split()))
pre=0
for i in m:
    #因为相同的会异或为0，剩下的就是不相同的，可以用来过滤出那个出现奇数次的
    pre^=i
print(pre)

采用异或的方法，可以用来过滤出现奇数次的那个数

发表于 2020-04-21 18:56:03 回复(0)

提交观点

问题信息

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

上传者：小小

难度：

26条回答 51收藏 6098浏览

通过挑战的用户

查看代码

牛客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

寻找奇数

输入描述:

输出描述:

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题