首页 > 试题广场 >

找出数组中只出现一次的数字

[编程题]找出数组中只出现一次的数字

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

输入一组未排序的整数，其中一个数字只出现一次，剩下的所有数字都出现了三次。找出这个只出现一次的数字。例如输入: [1,2,2,2,3,3,3]，输出为1

输入描述:

输入包含两行:
 第一行有一个整数n(1 ≤ n ≤ 100000),表示数组数字个数n,个数满足题意。 第二行为n个整数,范围均在32位整数,以空格分隔,保证输入数据合法

输出描述:

出现一次的那个数字

示例1

输入

7 1 2 2 2 3 3 3

输出

算法知识视频讲解

ぐ嚮穻同槕Ю,

public class problem2{
   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();
       }
       System.out.println(getResult(arr));
         sc.close();
   }
   public static int getResult(int arr[]){
                     int bits[]=new int[32];
                     int result=0;
                     for (int i = 0; i <arr.length; i++){
                        for (int j = 0; j < 32; j++)
                        bits[j] += ((arr[i] >> j) & 1);
                     }
                     for (int j = 0; j < 32; j++){
                        if (bits[j] % 3 != 0)
                            result += (1 << j);
                        }
                        return result;
      }

   }

发表于 2017-09-06 12:20:30 回复(0)

Python

南瓜风

Python解法（一）时间复杂度O（n）空间复杂度 O(1)

思路：若出现1次，将数给see_once，see_twice为0;若数出现两次，将数给see_twice,将see_once清0；若数出现三次，两个都清0；(适用于其他数出现次数为奇数的普遍情况，添加see_k-1即可)

import sys
n=int(sys.stdin.readline())
s=list(map(int,sys.stdin.readline().strip().split()))
see_once,see_twice=0,0
for i in s:
    see_once=~see_twice & (see_once^i)
    see_twice=~see_once & (see_twice^i)
print( see_once)

解法（二）：hashset ;时间、空间复杂度都为 O(n)

若有三个元素，c只出现一次，则 3*(a+b+c)-(a+a+a+b+b+b+c)=2c

程序也就一句话

import sys
n=int(sys.stdin.readline())
s=list(map(int,sys.stdin.readline().strip().split()))

print(3*sum(set(s))-sum(s))//2

编辑于 2020-04-06 22:36:25 回复(1)

Python

桃崽

def singleNumber(nums):
    
    return (3*sum(set(nums)) - sum(nums))//2
n=int(input())
num=[int(i) for i in input().split()]
print(singleNumber(num))

发表于 2020-03-21 14:30:36 回复(0)

offer給我，我要回家

import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int len=Integer.parseInt(sc.nextLine());
        String [] strs=sc.nextLine().split(" ");
        int [] nums=new int[len];     
            for(int i=0;i<len;i++){
           nums[i]=Integer.parseInt(strs[i]);
        }
                Arrays.sort(nums);
        for(int i=0;i<len;i+=3){
            if(i==len-1){
                System.out.println(nums[i]);
                System.exit(0);
            }
            int a=nums[i];
            int b=nums[i+1];
            if(a!=b){
                System.out.println(a);
                System.exit(0);
            }
          }
    }
}

编辑于 2019-09-18 11:39:28 回复(0)

元气の悟空

#include<stdio.h>
int sum[32],n,i,x,index,res=0;
int main(){
    for(scanf("%d",&n),i=0;i<n;i++){
        scanf("%d",&x),index=31;
        while(x) sum[index--]+=x%2,x/=2;
    }
    for(i=0;i<32;i++) res=res*2+sum[i]%3;
    printf("%d\n",res);
}//时间复杂度O(N),空间复杂度O(1)的解法

发表于 2017-10-31 13:05:00 回复(6)

牛客141580882号

先排序，再查找。

发表于 2021-10-13 08:48:58 回复(0)

fuxichen

#include<stdio.h>
int n,i,x,res=0;
int *array;
int main(){
    scanf("%d",&n);
    array=(int*)calloc(n,sizeof(int));
    for(i=0;i<n;i++){
        scanf("%d",&array[i]);
    }
    for(i=0;i<n;i++){
        x = array[i] ^ ( res ^ x);
        x^=res^=x^=res;
    };
    printf("%d\n",res);
}

发表于 2020-08-25 16:29:16 回复(0)

C/C++

1907040104张京

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
	int n, x, it, a[32] = { 0 },c , b = 0, res = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> x; it = 31;
		while (x)
		{
			c = x % 3;
			a[it--] += c;
			b = x / 3;
			x = b;
		}		
	}
	for (int i = 31; i >= 0; i--)
	{
		res += (a[i] % 3)* pow(3, 31 - i);
	}		
	cout << res << endl;
	return 0;
}

发表于 2020-08-10 18:21:28 回复(0)

tricoffee

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> a(n,0);
    for(int i=0;i<n;++i)
        cin>>a[i];
    sort(a.begin(),a.end());
    int cnt=1;
    for(int i=1;i<n;++i)
    {
        if(cnt==1&&a[i]!=a[i-1])
        {
            cout<<a[i-1]<<endl;
            return 0;
        }
        if(a[i]==a[i-1]) cnt+=1;
        else cnt=1;
    }
    return 0;
}

编辑于 2020-03-31 00:29:00 回复(0)

C/C++

牛客123313

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    map<int, int>mp;
    vector<int>data;
    for (int i = 0; i < n; i++)
    {
        int num;
        cin >> num;
        data.push_back(num);
        mp[data[i]]++;
    }
    for (int i = 0; i < n; i++)
    {
        if (mp[data[i]]==1)
        {
            cout << data[i];
        }
    }
    return 0;
}

发表于 2020-02-15 23:46:46 回复(0)

💦乐柠

import java.util.*;
public class Main {
    public static void main(String[] args){
       Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int array[] = new int[n];
        for(int i=0;i<n;i++){
            int num=s.nextInt();
            array[i]=num;
        }
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
            for(int i=0;i<array.length;i++){
               Integer num = (Integer) map.get(array[i]);
               //System.out.println(num);
               if(num!=null){
                   map.put(array[i], ++num);
               }else{
                   map.put(array[i], 1);
            }

            }
            Iterator it = map.keySet().iterator();
            b:while(it.hasNext()){
                int key = (Integer) it.next();
                int value = map.get(key);
                //System.out.print(key);
                //System.out.println(value);
                if(value==1){
                   System.out.println(key);
                   break b;
                }
                }
       }
}

发表于 2020-01-18 00:39:46 回复(0)

双笙20180911074448

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] a=new int[n];
        int sum=0;
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
      
        int x=0;
        for(int i=0;i<32;i++){//查看32个位置上面的数字为1的个数是否是3的倍数多1
           int bit=1<<i;
            int count=0;
            for(int j=0;j<n;j++){
               if((bit&a[j])!=0)
                   count++;
            }            
            if(count%3==1)//代表单独出现的那个数字在 1<<i这个位置上有出现1，故将其相加
                x=x|bit;
        }
        
           System.out.println(x);
    }
   
}

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

Java

一路顺疯951012

import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
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);
Stack<Integer> stack = new Stack<>();
for(int i=0;i<n;i++){
if(stack.isEmpty()||stack.peek()!=arr[i]){
stack.push(arr[i]);
}else{
stack.pop();
i=i+1;
}
}
int num = stack.pop();
System.out.println(num);
}
}

发表于 2019-09-12 17:00:27 回复(0)