一组带数字编号的球，其中有两个编号只出现了一次，把它们找出来

[编程题]一组带数字编号的球，其中有两个编号只出现了一次，把它们找出来

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

一组带数字编号的球里除了两个编号之外，其它的编号都出现了两次。
请写程序找出这两个只出现一次的编号。要求时间复杂度是O(n)，空间复杂度是O(1)。

输入描述:

整形数组
长度不超过1000000

输出描述:

输出数组中2个只出现了一次的数
先输出较小的数

示例1

输入

输出

1 6

备注:

可以考虑以以下代码作为模板，实现其中的getNumber()函数。

#include <bits/stdc++.h>
using namespace std;
int a[1000001];
void getNumber(const int a[], int n, int&num1, int&num2) {
//自行实现，要求时间O(n),空间O(1)。
}
int main(void) {
int n = 0;
while (~scanf("%d",&a[n+1])) ++n;
int p,q;
getNumber(a,n,p,q);
if (p>q) swap(p,q);
printf("%d %d\n",p,q);
return 0;
}

算法知识视频讲解

Java

大邮可为

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args)throws IOException{
        //Scanner sc = new Scanner(System.in);//会有复杂度过高的提示
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Set<Integer> set = new TreeSet<Integer>();// TreeSet：默认是按照升序排列
        String temp;
        while((temp=br.readLine())!=null){
            int num = Integer.valueOf(temp);
            if(set.contains(num))
                set.remove(num);
            else
                set.add(num);
        }
        for(Integer ob:set)
            System.out.print(ob+" ");
    }
}

发表于 2019-08-19 19:21:06 回复(0)