首页 > 试题广场 >

在其它数出现次数都为偶数的数组中找到出现次数为奇数次的数

[编程题]在其它数出现次数都为偶数的数组中找到出现次数为奇数次的数
  • 热度指数：1946 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给一个数组arr，其中只有一个数出现了奇数次，其它数出现了偶数次，打印这个数。

输入描述:
输出包含两行，第一行包含一个整数n，代表数组arr长度，第二行有n个数，代表数组arr。


输出描述:
输出一个整数，代表出现次数为奇数次的那个数。
示例1

输入

5
3 1 3 1 2

输出

2
示例2

输入

3
6 6 3

输出

3

备注:
时间复杂度,额外空间复杂度。
算法知识视频讲解
添加回答
B.F.-kenway头像 B.F.-kenway 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        int[] arr = new int[n];
        for(int i = 0;i < n;i++){
            arr[i] = sc.nextInt();
        }
        
        int res = findSingle(arr,n);
        System.out.println(res);
    }
    
    private static int findSingle(int[] arr,int n){
        int res = 0;
        for(int i = 0;i < n;i++){
            res ^= arr[i];
        }
        return res;
    }
}

发表于 2019-11-27 21:40:53 回复(0)
pein531头像 pein531
将数组中所有的数都进行异或操作，由于出现偶数次的数都会被自己和自己异或操作变成0，而0跟某个数num的异或结果为num，因此最终得到的结果就是那个出现了奇数次的数。 
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));
        int n = Integer.parseInt(br.readLine().trim());
        int remain = 0;
        String[] strArr = br.readLine().trim().split(" ");
        for(int i = 0; i < n; i++) remain ^= Integer.parseInt(strArr[i]);
        System.out.println(remain);
    }
}

发表于 2021-06-09 14:57:18 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

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

编辑于 2020-05-26 09:18:57 回复(0)
满足同盟头像 满足同盟
运用异或(^)的相关性质:
    a^a=0
    a^0=a
并且异或满***换律
那么我们可以维护一个变量ans,初值为0
每读入一个数就与ans进行异或
显然最终的ans就是出现次数为奇数的数
发表于 2019-11-05 18:10:50 回复(0)
Python 3
毓毓子最可爱头像 毓毓子最可爱 
e = 0
n = int(input())
arr = list(map(int, input().split()))
for i in arr:
    e ^= i
print(e)
整数n与0异或的结果时n，整数n与整数n异或的结果时0，用0异或数组中的数字，最后得到的就是出现次数为奇数的数字。
发表于 2022-04-03 11:53:33 回复(0)
Java
牛客908435449号头像 牛客908435449号 
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        int[] arr = new int[count];
        int res = 0;
        for(int i=0;i<count;i++){
            arr[i] = sc.nextInt();
            res ^= arr[i];
        }
        System.out.println(res);
    }
}

发表于 2022-01-13 11:08:20 回复(0)
Java
眼睛想旅行121头像 眼睛想旅行121 
import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        Arrays.sort(arr);
        for(int i=0;i<n-1;){
            if(arr[i]!=arr[i+1]){
                System.out.print(arr[i]);
                break;
            }
            i=i+2;
        }
    }
}

发表于 2021-03-31 14:08:20 回复(0)
程序猿的浪漫头像 程序猿的浪漫 
// 一股脑把数据都异或了再说
#include <iostream>
using namespace std;

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

发表于 2020-07-13 22:53:57 回复(0)
Java
求offerjava||bigdata头像 求offerjava||bigdata 
    public static void test(int[] data) {
        //题解： 例如 5^5=0。
        
        int flag = 0;
        for (int ele : data) {
            flag = flag ^ ele;
        }
        System.out.println(flag);
        
    }

发表于 2020-06-25 18:50:56 回复(0)
王仙客船长头像 王仙客船长 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, x;

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

发表于 2020-06-13 23:26:19 回复(0)
Timor炸弹头像 Timor炸弹
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int  t = 0;
        for(int i = 0; i < n; i++) {
            t ^= arr[i];
        }
        System.out.println(t);
    }
}
发表于 2020-05-08 23:41:37 回复(0)
夏花爱秋叶头像 夏花爱秋叶 
var len=parseInt(readline())
var arr=readline().split(' ').map(Number);
var my=[]
for(var i=0;i<len;i++){
    if(my.indexOf(arr[i])==-1){
        my.push(arr[i])
    }else{
        // 如果为偶数则删除
        my.splice(my.indexOf(arr[i]),1)
    }
}
console.log(my[0])

发表于 2020-04-18 17:32:37 回复(0)
剑走偏峰头像 剑走偏峰
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] ret = new int[n];
        for (int i = 0; i < n; i++) {
            ret[i] = scanner.nextInt();
        }
        Set<Integer> stack = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (stack.contains(ret[i])){
                stack.remove(ret[i]);
            }else {
                stack.add(ret[i]);
            }
        }
        int[] num = new int[stack.size()];
        for (int i = 0; i < stack.size(); i++) {
            Iterator<Integer> it = stack.iterator();
            while (it.hasNext()) {
                num[i] = it.next();
            }
        }
        Arrays.sort(num,0,stack.size());
        for (int i = 0; i < stack.size(); i++) {
            System.out.println(num[i]);
        }
    }
}
发表于 2019-12-25 13:25:27 回复(0)
汤普森30头像 汤普森30 
N = int(input())
nums = list(map(int, input().split()))
res = 0
for it in nums:
    res = res^it
print(res)

发表于 2019-08-25 11:35:15 回复(0)
提交观点

问题信息

位运算 数学 哈希
上传者：小小
难度：
14条回答 10703浏览

热门推荐

通过挑战的用户

查看代码

相关试题

在其它数出现次数都为偶数的数组中找到出现次数为奇数次的数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号