首页 > 试题广场 >

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

[编程题]一组带数字编号的球,其中有两个编号只出现了一次,把它们找出来
  • 热度指数:2888 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
一组带数字编号的球里除了两个编号之外,其它的编号都出现了两次。
请写程序找出这两个只出现一次的编号。要求时间复杂度是O(n),空间复杂度是O(1)。

输入描述:
整形数组
长度不超过1000000


输出描述:
输出数组中2个只出现了一次的数
先输出较小的数
示例1

输入

1
2
3
4
5
2
3
4
5
6

输出

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;
}
/*
异或运算 
出现两次的数异或为0,所有值异或等于两个只出现一次数的异或;
找到一个异或为1的位置t ,
位置t所有为0的值异或,所有为1的值异或,即为所求 
*/
#include <bits/stdc++.h>
using namespace std;
int a[1000001];
void getNumber(const int a[], int n, int&num1, int&num2)
{
    int i, yh = 0, t = 0;
    for(i = 1; i <= n; i++) {
        yh ^= a[i];
    }
    while((yh & 1) == 0) {
        t++;
        yh = yh >> 1;
    }
    num1 = 0;
    num2 = 0;
    for(i = 1; i <= n; i++) {
        if((a[i] >> t) & 1) num1 ^= a[i];
        else num2 ^= a[i];
    }

}
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;
}

发表于 2019-07-14 12:10:36 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a[1000003],n=0,x=0,y=0,s=0,t=0;
    while(cin>>a[n]){
        s ^= a[n];
        n++;
    }
    while((s&1)==0){
        t++;
        s >>= 1;
    }
    for(int i=0;i<n;i++){
        if((a[i]>>t)&1)
            x ^= a[i];
        else
            y ^= a[i];
    }
    cout<<min(x,y)<<" "<<max(x,y)<<endl;
    return 0;

}

发表于 2019-07-18 08:54:11 回复(0)
引用一篇文章。

思路:1)如果把数组中的所有数字都依次异或一遍,则可以消掉成对出现的数字,那么还有两个数字是单一的,肯定也不同,那么最终异或的结果肯定不是0。表示在二进制中肯定有一位是1,那么两个不同的数字,一定有一个在该位为1,另一个在该位为0。如果将整个数组按照该位是否为1分为两部分,那么这两部分各自包含一个单一数字。

2)分为两部分的数组,分别异或,最终结果就是这两个数。

3)注意:当然不用真的分成两个数组,按照条件查找,边查找,边异或就行了。
————————————————
版权声明:本文为CSDN博主「杜甫如诗」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/u013686654/article/details/76375369

发表于 2019-10-05 16:59:06 回复(0)
#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 res = 0;
    for (int i = 1; i <= n; ++i) {
        res ^= a[i];
    }

    // 以flg作为分隔两个出现一次数字的标记
    int flg = 1;
    while ((res & 1) == 0) {
        res >>= 1;
        flg <<= 1;
    }

    for (int i = 1; i <= n; ++i) {
        if (a[i] & flg) {    // 分组
            num1 ^= a[i];
        } else {
            num2 ^= a[i];
        }
    }
}
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;
}

发表于 2022-10-20 16:57:02 回复(0)
deffindNum(l):
    dic={}
    res=[]
    foriinrange(len(l)):
        ifdic=={}orl[i]notindic:
            dic[l[i]]=1
        else:
            dic[l[i]]+=1
    forkey,valindic.items():
        ifval==1:
            res.append(key)
    ifres[0] > res[1]:
        res[0],res[1]=res[1], res[0]
    returnstr(res[0])+' '+str(res[1])
l=[]
whileTrue:
    try:
        l.append(int(input()))
    except:
        break
print(findNum(l))
发表于 2021-03-12 21:11:06 回复(0)
import sys
nums = []
for num in sys.stdin.readlines():
    nums.append(int(num.strip()))
ans = 0
for d in nums:
    ans^=d 
x,y = 0,0
for d in nums:
    if d &(ans&(~ans+1))==0:
        x^=d 
    else:
        y^=d 
if x<y:
    print(x,y)
else:
    print(y,x)
    
   

发表于 2020-04-26 15:34:14 回复(0)
一下python代码只通过60%,应该是复杂度超时
self_list = []
while True:  
    try:
        a = raw_input()
        self_list.append(int(a))
    except:
        break
o = []
for r in self_list:
    c = self_list.count(r)
    if c == 1:
        o.append(r)
sorted(o)
print o[0], o[1]

发表于 2020-01-15 17:25:23 回复(0)
python93我佛了。一看标签C++好嘛,没对python加时。
光读数据都快超时了。
思路:剑指offer
先对所有数字异或一次,得到的是两个不成对的值的异或结果。
从这个结果中随便取出一位1。通过这个某一位的1把数据分成两部分,就是成对的数组中找到唯一一个不成对的题了。
/*
data = []
while(1):
    try:
        data.append(int(input()))
    except:
        break
cur = 0
for i in data:
    cur = cur^i
base = 1
while(base&cur)==0:
    base*=2;
cur1,cur2=0,0
for i in data:
    if i&base==0:
        cur1 = cur1^i
    else:
        cur2 = cur2^i
print(min(cur1,cur2),max(cur1,cur2))
*/
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<unsigned>data;
    unsigned tmp;
    while(cin>>tmp)
    {
        data.push_back(tmp);
    }
    unsigned res_two = 0;
    for(auto c:data)res_two^=c;
    unsigned cur = 1;
    while((res_two & cur)==0)
        cur*=2;
    unsigned res1=0,res2=0;
    for(auto c:data)
    {
        if((c & cur))
            res1^=c;
        else
            res2^=c;
    }
    cout<<min(res1,res2)<<" "<<max(res1,res2)<<endl;
}


发表于 2019-10-12 15:19:19 回复(0)
过了93.333%,提示超时。。。。这是为啥?大家不都用的这个方法嘛?
def getNumber(nums):
    t = 0
    for i in nums:
        t = t ^ i
    index = 0
    a, b = 0, 0
    while (t  & 1) == 0:
        t = t >> 1
        index += 1
    for i in nums:
        if ((i >> index) & 1) == 1:
            a = a ^ i
        else:
            b = b ^ i
    return a, b
if __name__ == "__main__":
    arr = []
    while True:
        try:
            arr.append(int(input()))
        except:
            break
    a, b = getNumber(arr)
    if a < b:
        print(a, b)
    else:
        print(b ,a)


发表于 2019-09-05 09:40:18 回复(0)
#include <iostream>
#include <vector>
using namespace std;
int main(void){
    int x, hash = 0, tag = 1, a = 0, b = 0;
    vector<int> v;
    while(cin>>x){
        v.push_back(x);
        hash ^= x;
    }
    while(!(hash & 1)){
        tag <<= 1;
        hash >>= 1;
    }
    for(int y : v){
        if(y & tag)
            a ^= y;
        else
            b ^= y;
    }
    if(a < b)
        cout<<a<<' '<<b<<endl;
    else
        cout<<b<<' '<<a<<endl;
    return 0;
}
所以数全部异或得到hash,hash中数位上为1表示这个数位上的a,b是不相同的,根据这个为判断将所有的数分为两类,相同的数肯定在同一类中,类中数再全部异或得到a,b的值
发表于 2019-08-26 15:35:02 回复(0)
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)
arr = []
while True:
    tmp = input()
    try: 
        tmp = int(tmp)
        arr.append(int(tmp))
    except:
        break
def isbit1(num, idx):
    num = num>>idx
    return num & 1
def findfirstbit(num):
    indexbit = 0
    while(num & 1==0):
        num=num>>1
        indexbit+=1
    return indexbit
i = 0
for k in arr:
    i = i^k
a,b,idx = 0,0,findfirstbit(i)
for i in arr:
    if isbit1(i,idx):
        a = a^i
    else:
        b = b^i
print(a,b)

发表于 2019-07-12 09:17:31 回复(0)
int[] nums={1,2,3,4,5,6,7,6,5,4,3,2,1};
        for(int i=0;i<nums.length;i++){
            
            int count=0;
            for(int j=0;j<nums.length;j++){
                if(nums[i]==nums[j]){
                    count++;
                }
            }
            if(count==1){
                System.out.print("只出现一次的编号:"+nums[i]);
                break;
            }
        }
记录数量为1的数字 .
发表于 2019-07-02 11:21:43 回复(1)
//开始用HashSet没通过,后来发现是Scanner的问题

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String temp;
        int cur;
        Set<Integer> set = new HashSet<>();
        while((temp=br.readLine())!=null){
            cur = Integer.parseInt(temp);
            if(set.contains(cur)){
                set.remove(cur);
            }else{
                set.add(cur);
            }
        }
        Iterator it = set.iterator();
        int a = (int) it.next();
        int b = (int) it.next();
        System.out.println(Math.min(a, b)+" "+Math.max(a,b));
    }
}

发表于 2019-06-30 20:58:31 回复(0)