首页 > 试题广场 > 在其它数出现次数都为偶数的数组中找到出现次数为奇数次的数
[编程题]在其它数出现次数都为偶数的数组中找到出现次数为奇数次的数
  • 热度指数:848 时间限制: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

备注:
时间复杂度,额外空间复杂度
#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)
将数组中所有的数都进行异或操作,由于出现偶数次的数都会被自己和自己异或操作变成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)
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)
运用异或(^)的相关性质:
    a^a=0
    a^0=a
并且异或满***换律
那么我们可以维护一个变量ans,初值为0
每读入一个数就与ans进行异或
显然最终的ans就是出现次数为奇数的数
发表于 2019-11-05 18:10:50 回复(0)
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)
    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)
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)
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)

问题信息

上传者:小小
难度:
12条回答 3390浏览

热门推荐

通过挑战的用户

查看代码