首页 > 试题广场 >

出现一次的数字ii

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

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

现在有一个整数类型的数组，数组中只有一个元素只出现一次，其余元素都出现三次。你需要找出只出现一次的元素

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

示例1

输入

[0,0,0,5]

输出

示例2

输入

[0]

输出

算法知识视频讲解

Java

シkid~

    public int singleNumber (int[] A) {
        // write code here
        int a = 0;
        int b = 0;
        // 卡诺图
        for(int c : A) {
            int temp1 = ((~a)&b&c) | (a&(~c));
            int temp2 = ((~a)&b&(~c)) | c&(~(a^b));
            a = temp1;
            b = temp2;
        }
        return b;
    }

发表于 2022-02-20 16:41:55 回复(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+3;
}
}
return 0;
// write code here
}

发表于 2021-09-08 21:15:01 回复(0)

Java

米咔米苏的零食

public class Solution {
    public int singleNumber (int[] A) {
        int i,j,k,l,count,flag=0;
                int []B=new int[10000];
        for(i=0,k=0,count=1;i<A.length;i++){
            count=1;
            for(j=i+1;j<A.length;j++){
                if(A[j]==A[i])
                    count++;
            }

            //遍历辅助数组看A[i]是否在B[l]中
            for(l=0;l<B.length;l++){
                if(B[l]==A[i]){
                    flag=1;
                    break;
                }
            }
            if(count>1&&flag==0)
                B[k++]=A[i];
            else
                flag=0;
        }
        for(i=0,flag=0;i<A.length;i++){
            for(j=0;j<B.length;j++){
                if(A[i]==B[j]){
                    flag=1;
                    break;
                }
            }
            if(flag==0)
                break;
            else
                flag=0;
        }
        return A[i];
    }
}

思路偏向于暴力，没有大佬们那么简单精辟的思路了。停留在使用flag水平的弱鸡。

开一个辅助数组，将出现了一次以上的数放进去，没放进去的就是答案要求的出现一次的数了。

发表于 2020-07-14 09:29:53 回复(0)

Java

AriesLi

分享一个通过真值表计算逻辑代数表达式的方法。

通过上一题我们知道可以通过异或运算留下只出现一次的值的数字的位值(A^~A=0)

这一题是否可以采用类似的思路呢？

当然是可以的，只不过对于此题，每个数字最多出现三次，也就是说通过位去计数的话，至少要两位才能记录下每一位出现的次数，我们假设计数N的高位为a，低位为b，循环遍历到的数字的当前位为c。

那么容易得到真值表：

a	b	c	结果a	结果b
0	0	0	0	0
0	1	0	0	1
1	0	0	1	0
0	0	1	0	1
0	1	1	1	0
1	0	1	0	0

通过真值表求逻辑代数的求解方法（请自行百度），可以得到：

resultA = (a&~b&~c) | (~a&b&c)

resultB = (~a&b&~c) | (~a&~b&c)

（不化简也能用，就不化简了，其实是运算律已经忘光了哈。）

如此，我们得到通过两个计数位去统计多个数字的某个位1出现的次数的方法，而且只有只出现一次的数字的当前位为1，b才会为1。

同理，我们将a和b拓展为整数，其每一位即统计的对应被统计的数组的数字位信息，按照如上逻辑代数表达式运算后，b的值就是只出现一次的整数值。

下面上代码：

public class Solution {
    public int singleNumber(int[] A) {
        int a = 0, b = 0;
        for(int c:A){
            int resultA = (a&~b&~c)|(~a&b&c);
            int resultB = (~a&b&~c)|(~a&~b&c);
            a = resultA;
            b = resultB;
        }
        return b;
    }
}

编辑于 2019-12-31 23:36:00 回复(0)

Java

吭哧吭哧埋头干

import java.util.HashMap;
public class Solution {
    public int singleNumber(int[] A) {
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<A.length;i++){
            if(map.containsKey(A[i])){
                map.put(A[i],map.get(A[i])+1);
            }else{
                map.put(A[i],1);
            }
        }
        for(int key:map.keySet()){
            if(map.get(key)!=3){
                return key;
            }
        }
        return 0;
    }
}

发表于 2018-05-30 19:25:57 回复(1)

Java

听见涛声~

public class Solution {
    public int singleNumber(int[] A) {
        int high = 0;
        int low = 0;
        for (int i = 0; i < A.length; i++) {
            high = high ^ (low & A[i]);
            low = low ^ A[i];

            int cohigh = high;
            high = high & (~low);
            low = low & (~cohigh);
        }
        return (high << 1) + low;
    }
}

用两个数的同一位分别来表示该位的高位和低位，以实现模3加法。

发表于 2018-04-29 13:33:19 回复(0)

Java

PG.13

//思路同single-number.先排序，然后顺序遍历，找不一样，返回，如果找不到，返回最后一个，注意数组越界。
//循环时候，i<A.length-1;
import java.util.*;
public class Solution {
public int singleNumber(int[] A) {
if(A.length==1){
return A[0];
}
Arrays.sort(A);
for(int i=0;i<A.length-1;i++){
if(A[i]!=A[i+1]){
return A[i];
}
i+=2;
}
return A[A.length-1];
}
}

发表于 2017-11-02 15:21:24 回复(0)

Java

无名huster

//由于只有一个出现一次的数字，其余都是出现三次，那么有如下思路
// 针对于序列中出现三次的所有数字的每一位来说，相加的结果只有两种
//1+1+1==3 或者0+0+0=0
//那么再加上只出现一次的数字的对应位数字的话，也有两种0或者4
//所以我们可以对上述的每一位求和之后对3取余，结果将会是1或者0
//也就是代表了出现一次的的这个数字对应位置上是1或者0
public class Solution {
    public int singleNumber(int[] A) {
        if(A == null||A.length == 0){
            return -1;
        }
        //得到出现一次的数字的值】
        int result = 0;
        //int为4个字节，那么一共有4*8=32位
        for(int i = 0;i < 32;i++){
            //保存每一位求和值
        	int sum = 0;
            for(int j = 0;j < A.length;j++){
                //累加所有数字上第i位上的数字
                sum+=(A[j]>>i)&1;
            }
            //取余得到第i位上的数字，之后更新result
            result |= (sum % 3) << i;
        }
        return result;
    }
}

发表于 2017-09-05 15:15:29 回复(2)

Java

爆破鬼才

/**

问题：

给定整数数组，除了一个元素外，每个元素出现3次，找到这个元素,提示：应该有运行时线性复杂度，不用额外内存

思路：

借助HashMap，遍历数组，对于数组中每项，第出现一次值加1,遍历map找到值为1的键值。

import java.util.*;

public class Solution {

public int singleNumber(int[] A) {

if(A==null||A.length==0)

return -1;

//String[] arr = new String[A.size()];

//map用来存储数值，以及出现的次数

HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();

int res = 0;

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

{

//如果包含原来值，则值+1

if(map.containsKey(A[i]))

{

map.put(A[i],map.get(A[i])+1);

}

else

{

//否则，初始化为1

map.put(A[i],1);

}

//遍历map值

Set<Integer> set = map.keySet();

for(Integer temp:set)

{

if(map.get(temp)==1)

{

res = temp;

break;

}

return res;

}

发表于 2017-08-01 08:32:55 回复(0)

Java

墨明棋妙pb

import java.util.*;

public class Solution {

public int singleNumber(int[] A) {

HashMap<Integer , Integer> map = new HashMap<Integer , Integer>();//用来相应整数出现的次数

int length = A.length;

if(length == 0)

return -1;

if(length == 1)

return A[0];

for(int i = 0 ; i < length ; i++)

{

if(!map.containsKey(A[i]))

{

map.put(A[i] , 1);

}

else if(map.containsKey(A[i]))

{

int sum = map.get(A[i]);

map.put(A[i] , sum+1);

}

for(int j = 1 ; j < length ; j++)

{

if(map.get(A[j]) == 1)

{

return A[j];

}

return -1;

}

发表于 2017-07-25 20:28:05 回复(1)

Java

油头教授的坩埚

public int singleNumber(int[] nums) { int ans = 0; for(int i = 0; i < 32; i++) { int sum = 0; for(int j = 0; j < nums.length; j++) { if(((nums[j] >> i) & 1) == 1) { sum++; sum %= 3;
            }
        } if(sum != 0) {
            ans |= sum << i;
        }
    } return ans;
}