首页 > 试题广场 >

出现一次的数字

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

热度指数：38275 时间限制：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)

Werial

异或只适用于出现偶数次相同的数字，且只有一个不同的出现；如果是大于2个的出现的奇数次，那就不适用，此题的难度就编为中等了；

发表于 2021-01-05 11:27:12 回复(0)

C/C++

wydxry

class Solution {
public:
    int singleNumber(int A[], int n) {
        if(n==0) return 0;
        int tmp=A[0];
        for(int i=1;i<n;i++){
            tmp^=A[i];
        }
        return tmp;
    }
};

发表于 2020-04-12 17:14:19 回复(0)

胖十斤换网名的阿琛

//不是不可以开辟额外空间吗?

class Solution {
public:
    int singleNumber(int A[], int n) {
        for(int i = 1;i < n;++i)
            A[0] ^= A[i];
        return A[0];
    }
};

发表于 2019-10-08 15:18:38 回复(0)

xxj

class Solution {
public:
int singleNumber(int A[], int n) {
int r = 0;
for(int i=0;i<n;i++)
r ^= A[i];
return r;
}
};

发表于 2014-11-14 10:54:37 回复(0)

T+T

其实只要记住：

1.异或满***换律。

2.相同两个数异或为0。

3.0异或一个数为那个数本身。

最后结果即出现1次的那个数。

public int singleNumber(int[] A) {

int res=0;

for (int i=0;i<A.length;i++){

res^=A[i];

}

return res;

}

发表于 2017-03-28 16:05:24 回复(7)

hardy

两个相同的数异或结果为0，不同为1 ，根据该规则下列过程如下

假设数组为 2,3,2,3,4,1,4

那么结果应该为1

2^3=0000 0010 ^ 0000 0011 = 0000 0001 1

1^2=0000 0001 ^ 0000 0010 = 0000 0011 3

3^3=0000 0011 ^ 0000 0011 = 0000 0000 0

0^4=0000 0000 ^ 0000 0100 = 0000 0100 4

4 ^ 1 =0000 0100 ^ 0000 0001 = 0000 0101 5

5 ^ 4= 0000 0101 ^ 0000 0100 =0000 0001 1

整个过程如上，最后结果为1

发表于 2016-08-11 12:47:49 回复(0)

あのあの

//
class Solution {
public:
    //因为A XOR A = 0，且XOR运算是可交换的，于是，对于实例{2,1,4,5,2,4,1}就会有这样的结果：
    //(2^1^4^5^2^4^1) => ((2^2)^(1^1)^(4^4)^(5)) => (0^0^0^5) => 5
    int singleNumber(int A[], int n) 
    {
        int result =0;
        for(int i=0;i<n;i++)
            result^=A[i];
        return result;
    }
};

发表于 2018-06-12 12:59:42 回复(1)

从前从前有个人爱你很久

//思路：两个相同的数异或为0
//例子:1^2^3^4^4^3^2 = 2^2^3^3^4^4^1 = 1
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;
    }
}

发表于 2017-03-16 14:01:23 回复(3)

C/C++

class Solution {
public:
    int singleNumber(int A[], int n) 
    {
        sort(A,A+n);
        for(int i=0;i<n-1;i+=2)    
        {
            if(A[i]!=A[i+1])
                return A[i];
        }
        return A[n-1];
    }
};

发表于 2017-07-05 16:16:50 回复(0)

lanxuewei

package test;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/**
 * @param lanxuewei
 * 一个数组中除一个数字X外其他每个数字都出现两次，找出这个数字X
 * */
public class SingleNum1 {

	/**
	 * 遍历数组，判断当前数字是否存在于Set集合中，如果存在则删除，不存在则加入。
	 * 最后只剩下只出现一次的数字X，返回即可。
	 * 拓展：如果出现多个只出现一次的数字同样适用，不需要遍历，直接返回set即可。
	 * */
	public int simgleNum(int[] A){
		Set<Integer> set = new HashSet<Integer>();
		int result = 0;
		
		for(int i = 0; i <= A.length - 1; i++){
			if(set.contains(A[i])){
				set.remove(A[i]);
			} else {
				set.add(A[i]);
			}
		}
		Iterator<Integer> it = set.iterator();
		while(it.hasNext()){
			result = it.next();
		}
		return result;
	}
	
	public static void main(String[] args) {
		//测试数据
		int arr[] = {1,2,2,3,3,4,4,5,5};
		SingleNum1 test = new SingleNum1();
		System.out.println(test.simgleNum(arr));
	}

}

编辑于 2017-07-26 13:58:26 回复(1)

SharkIng

这题明明没写错可是为什么output不对呢？

发表于 2014-10-02 10:15:29 回复(2)

Java

还没xiang好

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)

WindedMan

//直接异或即可

int singleNumber(int A[], int n) {
        int one=0;
        for(int i=0;i<n;i++){
            one^=A[i];
        }
        return one;
    ｝

发表于 2020-03-16 22:17:41 回复(0)

同桌冋宇

/**
* Created by Mr SJL on 2016/11/18.
*
* @author Junlan Shuai
*/
public class Solution
{
    public int singleNumber(int[] A)
    {
        // 先对数组进行排序
        selectionSort(A);
        // 每相邻两位相等，不等则输出
        for (int k = 0; k < A.length-1; k += 2)
        {
            if (A[k] != A[k + 1])
            {
                return A[k];
            }
        }
        return A[A.length-1];
    }

    /**
     * 选择排序
     * @param A
     */
    public void selectionSort(int[] A)
    {
        for (int i = 0; i < A.length; i++)
        {
            int max = i;
            for (int j = i + 1; j < A.length; j++)
            {
                if (A[j] > A[max])
                {
                    max = j;
                }

            }
            swap(A, i, max);
        }
    }
    public void swap(int[] A, int a, int b)
    {
        int t = A[b];
        A[b] = A[a];
        A[a] = t;
    }
}

发表于 2016-11-18 20:26:03 回复(0)

林深鹿鸣

利用异或的开关性，遍历即可，推荐一道类似的但需要另外一些技巧的题目http://acm.zzu.edu.cn:8000/problem.php?id=10450

发表于 2016-06-23 13:15:09 回复(0)

牛客304487号

  classSolution { 

  public: 

      intsingleNumber(intA[], intn) 

      { 

          if(n==1) 

              { 

              returnA[0]; 

          } 

          while(n>=2) 

              { 

              A[n-2]^=A[n-1]; 

              n--; 

          } 

          returnA[0]; 

      } 

  }; 

  没有额外内存

发表于 2015-06-01 11:06:16 回复(3)

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)

达子0920

public int singleNumber (int[] intArr) {
    // write code here
    if(intArr.length == 0) {
        return 0;
    }
    if(intArr.length == 1) {
        return intArr[0];
    }
    Arrays.parallelSort(intArr);
    for(int i = 0; i < intArr.length; i++) {
        if(intArr[i] != intArr[i+1]) {
            return intArr[i];
        }
        i++;
    }
    return 0;
}

先排序，再两两对比

发表于 2020-10-17 14:22:46 回复(0)

金虹桥招财猫

class Solution {

public int singleNumber(int[] nums) {

//异或NBBBBBBBBB~~~~~~~

//以nums[0]为基准

int result = nums[0];

if(nums.length > 1){

//nums[1]开始异或到最后同的全归零

for(int i = 1; i<nums.length; i++){

result = result^nums[i];

}

return result;

}

发表于 2020-07-10 13:14:44 回复(0)

AriesLi

如果两个数以上通过异或判断不出来，可以推导构造一个新的逻辑运算。

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

发表于 2019-12-31 17:59:25 回复(0)