首页 > 试题广场 >

数组中值出现了一次的数字

[编程题]数组中值出现了一次的数字
  • 热度指数：2330 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个数字arr，其中只有有两个数字出现了奇数次，其它数字都出现了偶数次，按照从小到大顺序输出这两个数。

输入描述:
输入包含两行，第一行一个整数n，代表数组arr的长度，第二行n个整数，代表数组arr,arr[i]为32位整数。


输出描述:
输出出现奇数次的两个数，按照从小到大的顺序。
示例1

输入

4
1 1 2 3

输出

2 3
示例2

输入

6
11 22 11 23 23 45

输出

22 45

备注:
时间复杂度,额外空间复杂度。
算法知识视频讲解
添加回答
Spectre_头像 Spectre_ 
#include<iostream>

int main() {
    int n, temp = 0, bit, res1 = 0, res2 = 0;
    std::cin >> n;
    int array[n];
    for (int i = 0; i < n; ++i) std::cin >> array[i];
    for (int i = 0; i < n; ++i) temp ^= array[i];
    bit = temp & (~temp + 1);
    for (int i = 0; i < n; ++i) {
        if ((bit & array[i]) == 0) res1 ^= array[i];
        else res2 ^= array[i];
    }
    std::cout << (res1 < res2 ? res1 : res2) 
        << " " << (res1 > res2 ? res1 : res2);
    
    return 0;
}

发表于 2021-09-06 22:39: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;
        }
        for(int i=n-1;i>1;){
            if(arr[i]!=arr[i-1]){
                System.out.print(arr[i]);
                break;
            }
            i=i-2;
        }
    }
}

发表于 2021-03-31 14:13:40 回复(0)
Java
屈萌头像 屈萌 
import java.util.*;

public class Main2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }
            int retExclusive = 0;
            for (int i = 0; i <n ; i++) {
                retExclusive^=arr[i];
            }
            int index = findIndex(retExclusive);
            int num1 = 0;
            int num2 = 0;
            for (int i = 0; i <n ; i++) {
                if (judgeIndex(arr[i],index)){
                    num1^=arr[i];
                }else{
                    num2^=arr[i];
                }
            }
            if (num1<num2){
                System.out.println(num1+" "+num2);
            }else{
                System.out.println(num2+ " " + num1);
            }
        }
        }
        public static int findIndex(int num){
        //在整数num中找到最右边是1的位置
        int index = 0;
        while ((num&1)==0){
            num>>=1;
            index++;
        }
        return index;
        }
        public static boolean judgeIndex(int num,int index){
        //判断整数num右边第num位是否为1
        num>>=index;
        return ((num&1)==1);
        }
}

发表于 2020-06-11 15:04:46 回复(1)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, s=0, t=0, x=0, y=0;
    scanf("%d", &n);
    int a[n];
    for(int i=0;i<n;i++){
        scanf("%d", &a[i]);
        s ^= a[i];
    }
    t = s & (-s);
    for(int i=0;i<n;i++)
        if(a[i] & t)
            x ^= a[i];
    x = min(x, x^s);
    y = max(x, x^s);
    printf("%d %d\n", x, y);
    return 0;
}

发表于 2020-06-06 10:11:43 回复(0)
Jasonyou头像 Jasonyou
import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args){
        Scanner in= new Scanner(System.in);
        int n= in.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=in.nextInt();
        }
        int eor=0;
        for(int i=0;i<n;i++){
            eor=eor^arr[i];
        }

        // 不同位所在位置
        int eor0=eor&(~eor+1);
        int a=0;
        for(int i=0;i<n;i++){
            // 只取该位中为0的位置，要么包括a，要么b
            if((eor0&arr[i])==0){
                a=a^arr[i];
            }
        }
        int b=eor^a;
        if(a>b){
            int temp=a;
            a=b;
            b=temp;
        }
        System.out.printf("%d %d",a,b);
    }
}
发表于 2024-09-01 15:21:49 回复(0)
冰狗Y头像 冰狗Y
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
     public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int length = in.nextInt();
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int[] arr = new int[length];
            for (int i = 0; i < length; i++) {
                int b = in.nextInt();
                arr[i] = b;
            }

            HashMap<Integer, Integer> countMap = new HashMap<>();

            //统计每个数字出现的次数
            for (int num : arr) {
                //如果key=num时有值，则返回这个值，如果没有，则默认为0
                Integer count = countMap.getOrDefault(num, 0);
                //把存入map里的key的值在原有的基础上+1
                countMap.put(num, count + 1);
            }

            // 使用 TreeSet 来存储按从小到大排序的数字
            TreeSet<Integer> sortedSet = new TreeSet<>();
            //将奇数项存入TreeSet中
            for (int num : countMap.keySet()) {
                if (countMap.get(num) % 2 != 0){
                    sortedSet.add(num);
                }
            }

            //遍历TreeSet并取出
            for (int num : sortedSet) {
                System.out.print(num+" ");
            }
        }
     }
}
发表于 2023-06-30 22:03:57 回复(0)
牛客79631828号头像 牛客79631828号 
import java.util.*;

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[] res = getOnceNum(arr);
        System.out.println(res[0] + " " + res[1]);
        sc.close();
    }
    
    public static int[] getOnceNum (int[] arr) {
        int eor = 0;
        //因为a ^ a = 0, 所以所有出现偶数次的数都被消掉了，
        //剩下的eor结果为A ^ B (A与B为只出现奇数次的数)
        for (int cur : arr) {
            eor ^= cur;
        }
        int[] res = new int[2];
        //因为两者不等，异或肯定不为0，找出结果中最右的1
        int rightOne = eor & (~eor + 1);
        int eorOne = 0;
        //异或结果在某一位为1的前提是A与B在该位置不同，找出在那个位置为1的数
        //在那个位置为1的出现奇数次的数只有一个，其他出现偶数次的数都会被消掉
        for (int cur : arr) {
            if ((cur & rightOne) != 0) {
                eorOne ^= cur;
            }
        }
        //若a ^ b = c，则a = c ^ b 且 b = c ^ a
        int eorZero = eor ^ eorOne;
        res[0] = eorZero > eorOne ? eorOne : eorZero;
        res[1] = res[0] == eorZero ? eorOne : eorZero;
        return res;
    }
}

编辑于 2021-08-09 20:12:05 回复(0)
kevin_Wang333头像 kevin_Wang333 


import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Question1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<Integer> arrayList = new ArrayList<>();
        ArrayList<Integer> result = new ArrayList<>();
        int n = scanner.nextInt();
        for(int i = 0;i < n;i++) {
            arrayList.add(scanner.nextInt());
        }
        Collections.sort(arrayList);
        int a = arrayList.get(0);
        int flag = 0;
        int j = 0;
        while(j < n) {
            while (j < n && a == arrayList.get(j)) {
                flag++;
                j++;
            }
            if(flag % 2 == 1) {
                result.add(arrayList.get(j - 1));
            }
            if(j < n) {
                a = arrayList.get(j);
            }
            flag = 0;
        }
        System.out.println(result.get(0) + " " + result.get(1));
    }
}
发表于 2020-07-17 23:37:57 回复(0)
Java
只求一个offer！！！！头像 只求一个offer！！！！ 
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNext()){
            int n = in.nextInt();
            int[]num = new int[n];
            int[]num1 = new int[2];
            Map<Integer,Integer> map = new HashMap<>();
            for (int i = 0; i < n ; i++) {
                num[i] = in.nextInt();
            }
            for (int j = 0; j < n ; j++) {
                if(map.containsKey(num[j])){
                    map.put(num[j],map.get(num[j])+1);
                }else {
                    map.put(num[j],1);
                }
            }
            int k =0;
            for (Integer key:map.keySet()) {
                if(map.get(key)%2!=0){
                    num1[k] = key;
                    k++;
                }

            }
            Arrays.sort(num1);
            String a ="";
            a =num1[0]+" "+num1[1];
            System.out.println(a);

        }
    }
}

哈希表
发表于 2020-07-17 10:46:34 回复(0)
Java
阮梦头像 阮梦
求助，代码通过率只有60%，大家帮忙改一改

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int  array[] = new int[n];
        for(int i = 0; i<n; i++){
            array[i] = sc.nextInt();
        }
        int ret = 0;
        for(int x:array){
            ret^=x;
        }
        int i = 0;
        for(;i<32;i++){
            if((ret&(1<<i))==1)
                break;
        }
        int a = 0; int b = 0;
        for(int x:array){
            if((x&(1<<i))==1){
                a^=x;
            }else{
                b^=x;
            }
        }
        if(a<b){
            System.out.println(a+" "+b);
        }else{
            System.out.println(b+" "+a);
        }
    }
}

发表于 2020-06-20 23:46:24 回复(1)
小凯凯呢头像 小凯凯呢
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
public class Main {
    public static void func(int[] arr){
        Map<Integer,Integer> map=new TreeMap<>();
        for(Integer c:arr){
            int k=map.getOrDefault(c,0);
            map.put(c,k+1);
        }
        for(Map.Entry<Integer,Integer> e:map.entrySet()){
            if(e.getValue()%2==1){
                System.out.print(e.getKey()+" ");
            }
        }
        System.out.print("\n");
    }
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=scanner.nextInt();
        }
        func(arr);
    }
}
发表于 2020-04-27 11:55:48 回复(0)
华未央头像 华未央 
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n,t;
    int x=0;
    int in=1;
    int y=0,z=0;
    vector<int> vec;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>t;
        vec.push_back(t);
    }
    for(int i=0;i<n;i++)
        x^=vec[i];
    while((x&1)==0)//得到两奇数次的数字在哪一位不相同
    {
        in<<=1;
        x>>=1;
    }

    for(int i=0;i<n;i++)//将原数组分成两部分，分别得到数字
    {
        if((vec[i]&in)==0)
            y^=vec[i];
        else
            z^=vec[i];
    }
    if(y>z)//从小到大排序
    {
        y=y^z;
        z=y^z;
        y=y^z;
    }
    cout<<y<<" "<<z;
    return 0;
}

编辑于 2020-03-16 18:41:34 回复(0)
Java
大小虎头像 大小虎 
import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
        //这块不是很懂，使用nextInt接收个数时，还未输入具体数字 nextLine后面的代码也会执行
            String s=sc.nextLine();
            String s1=sc.nextLine();
            String[]  ss=s1.split(" ");
            Map<String,Integer> mm=new HashMap<String,Integer>();
            for(int i=0;i<ss.length;i++){
                //偶数最终将不在map中
                if(mm.containsKey(ss[i])){
                    mm.remove(ss[i]);
                }else{
                    mm.put(ss[i],1);
                }
            }
            Set<Entry<String,Integer>>  es=mm.entrySet();
            int [] arr=new int[2];
            for(Map.Entry<String,Integer>  en:es){
                if(arr[0]==0){
                arr[0]=Integer.parseInt(en.getKey());
                }else{
                    arr[1]=Integer.parseInt(en.getKey());
                }
            }
                  if(arr[0]>arr[1]){
                    arr[0]=arr[0]^arr[1];
                     arr[1]=arr[0]^arr[1];
                      arr[0]=arr[0]^arr[1];
        }
       System.out.println(arr[0]+" "+arr[1]);
        }
  
    }
}


编辑于 2019-10-16 21:49:24 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

数组中值出现了一次的数字

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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