我要招人

去企业版

首页 > 试题广场 >

出现一次的数字

[编程题]出现一次的数字

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

现在有一个整数类型的数组，数组中素只有一个元素只出现一次，其余的元素都出现两次。

数据范围： $0 < n \le 4000$ ，数组中每个值满足 $0 \le val \le 4000$
进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

[1,0,1]

输出

示例2

输入

[0]

输出

算法知识视频讲解

推荐

StrongYoung

根据异或运算特点：

两个相同的数进行异或，结果为0

	public static int singleNumber(int[] A) {
		int num = 0;
		for(int i=0;i<A.length;i++){
			num^=A[i];
		}
		return num;
	}

编辑于 2016-07-13 21:30:50 回复(15)

Java

墨染加油当大牛

先用hashmap存储出现的次数，再返回次数为1的元素：
HashMap<Integer, Integer> countMap = new HashMap<>();

for (int i : A) {

countMap.put(i, countMap.getOrDefault(i, 0) + 1);

}

for (Integer i : countMap.keySet()) {

if (countMap.get(i).equals(1)) {

return i;

}

发表于 2023-11-22 17:55:42 回复(0)

Java

莱特雷

import java.util.*;

public class Solution {
    public int singleNumber (int[] A) {
        int result = A[0];
        for(int i=1; i<A.length; i++) {
            result ^= A[i];
        }
        return result;
    }
}

发表于 2021-11-15 20:53:09 回复(0)

Java

岛。201904182324772

public int singleNumber (int[] A) {
if(A.length==0) return 0;
Arrays.sort(A);
int i=0;
while(i<A.length){
if(i==A.length-1 || A[i]!=A[i+1]){
return A[i];
}else{
i=i+2;
}
}
return 0;
// write code here
}

发表于 2021-09-08 21:39:27 回复(0)

Java

Tod_

import java.util.*;


public class Solution {
    /**
     * 
     * @param A int整型一维数组 
     * @return int整型
     */
    public int singleNumber (int[] A) {
        // write code here
        int res = A[0];
        for(int i=1; i<A.length; i++){
            res ^= A[i];
        }
        return res;
    }
}

发表于 2021-03-11 14:08:12 回复(0)

Java

werr370

    public int singleNumber (int[] A) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<A.length;i++){
            if(!map.containsKey(A[i])){
                map.put(A[i],1);
            }else{
                map.put(A[i],map.get(A[i])+1);
            }
        }
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(entry.getValue()==1){
                return entry.getKey();
            }
        }
        return 0;
    }
}

    public int singleNumber (int[] A) {
        int result=0;
        for(int i=0;i<A.length;i++){
            result^=A[i];
        }
        return result;

    public int singleNumber (int[] A) {
        if(A.length==1){
            return A[0];
        }
        Arrays.sort(A);
        for(int i=0;i<A.length-1;i+=2){
            if(A[i]!=A[i+1]){
                return A[i];
            }
        }
        return 0;

编辑于 2020-12-09 15:13:21 回复(0)

Java

Double厚

n ^ n = 0

n ^ 0 = n

public int singleNumber(int[] A) {
    int res = 0;
    for (int x : A) {
        res ^= x;
    }
    return res;
}

发表于 2020-10-27 18:29:36 回复(0)

Java

tornado123

public class Solution {
    /**
     * 
     * @param A int整型一维数组 
     * @return int整型
     */
    public int singleNumber (int[] A) {
        // 可以对整个数组 A 进行一个异或操作，因为相同的两个数异或结果为0 ，一个数与0异或等于这个数本身
        int result = 0;
        for (int i = 0; i < A.length; i++) {
            result ^= A[i];
        }
        return result;
    }
}

发表于 2020-10-14 09:51:46 回复(0)

Java

hshorse168

public class Solution {
    public int singleNumber(int[] A) {
        int result = A[0];
        for(int i=1; i<A.length; i++){
            result = result ^ A[i];
        }
        return result;
    }
}

发表于 2018-09-26 18:13:23 回复(0)

Java

jRomann

public class Solution {
    public int singleNumber(int[] A) {
        int sum=0;
        for(int i=0;i<A.length;i++){
            sum = sum^A[i];
        }
        for(int i=0;i<A.length;i++){
            if( (A[i]^sum) == 0){
                return A[i];
            }
        }
        return 0;
    }
}

发表于 2018-05-08 11:05:16 回复(0)

Java

七仔0312

2^2=0 0^2=2;

```

public class Solution {
public int singleNumber(int[] A) {
int result = A[0];
for (int i = 1; i < A.length; i++) {
result ^= A[i];
}
return result;
}
}

```

发表于 2018-03-29 22:07:11 回复(0)

Java

咖啡新东方

不用额外空间的话只能用循环咯，偷懒没用Integer.min

public int singleNumber(int[] A) {
if(A.length==1) return A[0];
for(int i=0;i<A.length-1;i++){
for(int j=i+1;j<A.length;j++){
if(A[i]==A[j]&&A[i]!=-9999){
A[i] = -9999;
A[j] = -9999;
}
}
}
for(int i=0;i<A.length;i++){
if(A[i]!=-9999) return A[i];
}
return -9999;
}

发表于 2018-03-10 23:43:03 回复(0)

Java

小白VI

import java.util.*;
public class Solution {
    public int singleNumber(int[] A) {
        Arrays.sort(A);
        int len=A.length;
        for(int i=0;i<len-2;i+=2){
            if(A[i]!=A[i+1])
                return A[i];
        }
        return A[len-1];
    }
}

# Python
# 
# @param A int整型一维数组 
# @return int整型
#
class Solution:
    def singleNumber(self , A ):
        # write code here
        for i in A:
            if A.count(i) == 1:
                return i

编辑于 2021-03-17 16:05:49 回复(0)

Java

傻傻傻傻

/**
数组中只有一个元素出现1次，其他元素都出现了2次
要求：在O(N)时间复杂度情况下，找出只出现1次的那个元素
注：不能使用额外空间
*/
public class Solution {
    public int singleNumber(int[] A) {
        if (A.length < 1)
            return 0;
        int result = A[0];
        for (int i = 1; i < A.length; i++) {
            result ^= A[i];
        }
        return result;
    }
}

编辑于 2017-11-27 16:51:54 回复(0)

Java

PG.13

import java.util.Arrays;
//思路：先排序，然后两两比较，如果后一个不等于前一个，那么前一个就是要找的数据，如果找不到，最后一个落单。
//复杂度o(n)
public class Solution {
public int singleNumber(int[] A) {
if(A.length==1){
return A[0];
}
Arrays.sort(A);
for(int i=1;i<A.length;i++){
if(A[i]!=A[i-1]){
return A[i-1];
}
i++;
}
return A[A.length-1];
}
}

发表于 2017-11-02 15:06:01 回复(0)

Java

无名huster

//相同的数字进行异或操作则结果为0，那么遍历数组
//有相同数字的情况下异或操作结果为0，最后就是0^单独出现一次的数字
public class Solution {
    public int singleNumber(int[] A) {
        int temp = 0 ;
        if(A == null||A.length==0){
            return -1;
        }
        for(int i = 0;i < A.length;i++){
            temp = temp ^ A[i];
        }
        return temp;
    }
}

发表于 2017-09-05 11:15:27 回复(0)

Java

nikfce

public class Solution {
    public int singleNumber(int[] A) {
        int one = 0;
        for (int a : A) one ^= a;
        return one;
    }
}

发表于 2017-08-11 18:39:49 回复(0)

Java

pp11

public class Solution {
    public int singleNumber(int[] A) {
        if (A == null || A.length == 0)
            return -1;
        int result = A[0];
        for (int i = 1; i < A.length; ++i){
            result ^= A[i];
        }
        return result;
    }
}

发表于 2017-07-17 22:18:07 回复(0)