首页 > 试题广场 >

数组中只出现一次的数（其它数出现k次）

[编程题]数组中只出现一次的数（其它数出现k次）

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

给定一个长度为 n 的整型数组 arr 和一个整数 k(k>1) 。

已知 arr 中只有 1 个数出现一次，其他的数都出现 k 次。

请返回只出现了 1 次的数。

数据范围: $1 \le n \le 2*10^5$ ， $1 \lt k \lt 100$ ， $-2*10^9 \le arr[i] \le 2*10^9$

进阶：时间复杂度 $O(32n)$ ，空间复杂度 $O(1)$

示例1

输入

[5,4,1,1,5,1,5],3

输出

示例2

输入

[2,2,1],2

输出

算法知识视频讲解

橙木

一开始想的是既然有几组相同的数据，那么我将其所有的求和然后处以k就可以了，例如（5，5，4，4，1），就是19%2，但是发现这种情况只适用于单独的数据不大于k的情况，如果把1换成3就不成立了

后面看到题目考的是位运算的提示，既然不能整体数据直接相加，那就把数据每个位相加吧，对于相同的数据该位肯定会有k组

例如上面的对应位累加求和后是413的结果，取余掉多余的部分，则得到011，也就是我们所求的数据

发表于 2021-05-20 15:00:21 回复(1)

Roxannekkk

方法一：判断k的奇偶性值，如果是偶数，利用异或，若为奇数，可以利用hashmap来完成

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr int一维数组 
     * @param k int 
     * @return int
     */
    public int foundOnceNumber (int[] arr, int k) {
        // write code here
        int n=arr.length;
        if(k%2==0){
            //偶数
            int ans=0;
            for(int i=0;i<n;i++){
                ans^=arr[i];
            }
            return ans;
        }
        else{
            Map<Integer,Integer> hashmap=new HashMap();
            for(int i=0;i<n;i++){
                hashmap.put(arr[i],hashmap.getOrDefault(arr[i],0)+1);
            }
             for(Map.Entry<Integer,Integer> entry:hashmap.entrySet()){
                if(entry.getValue()==1) return entry.getKey();
            }
        }
        return -1;
    }
}

方法二：位运算

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr int一维数组 
     * @param k int 
     * @return int
     */
    public int foundOnceNumber (int[] arr, int k) {
        // write code here
        int n=arr.length;
        int[] ans=new int[32];
        for(int i=0;i<n;i++){
            for(int j=0;j<32;j++){
                ans[j]+=arr[i]&1;
                arr[i]>>>=1;
            }
        }
        int res=0;
        for(int i=0;i<32;i++){
            res<<=1;
            res|=ans[31-i]%k;
            
        }
        return res;
    }
}

编辑于 2021-06-29 11:40:28 回复(1)

C/C++

薇笑倩兮

int foundOnceNumber(vector<int>& arr, int k) {
        // write code here
        sort(arr.begin(),arr.end());
        for(int i=0;i<arr.size()-k+1;i+=k){
            if(arr[i]!=arr[i+k-1]) return arr[i];
        }
        return arr[arr.size()-1];
        
    }

发表于 2021-02-16 22:17:42 回复(1)

Java

陈少年

//利用数组

Arrays.sort(arr);

for(int i=0; i<arr.length;i++){
if (arr[arr.length-1]!=arr[arr.length-2])
return arr[arr.length-1];
if(arr[i]==arr[i+1]){
i=i+k-1;
}
else{
int s=arr[i];
return s;
}
}return 0;

}

发表于 2021-08-22 18:47:54 回复(0)

Java

huangziqiang

//方法一：利用Map集合
/*
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (!map.containsKey(arr[i])) map.put(arr[i],1);
            else map.put(arr[i],map.get(arr[i]) + 1);
        }
        int res = 0;
        for (int key : map.keySet()){
            if (map.get(key) == 1){
                res = key;
            }
        }
        return res;
*/

        //方法二：同时利用List、Set两个集合
/*
        List<Integer> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            if (!list.contains(arr[i])) {
                list.add(arr[i]);
                set.add(arr[i]);
            }
            else set.remove(arr[i]);
        }

        int res = 0;
        for (int ele : set){
            res = ele;
        }
        return res;
*/

        //方法三：利用数组
///*
        Arrays.sort(arr);
        for (int i = 1; i < arr.length - 1; i++) {
            if (arr[i] != arr[i - 1] && arr[i] != arr[i + 1]) return arr[i];
        }
        if (arr[0] != arr[1]) return arr[0];
        else return arr[arr.length - 1];
//*/

        //方法四：两层暴力for循环（思路上可行，但时间复杂度o(n^2),可能运行超时）
/*
        for (int i = 0; i < arr.length; i++) {
            int count = 0;
            for (int j = 0; j < arr.length; j++) {
                if (arr[i] == arr[j]) count++;
            }
            if (count == 1) return arr[i];
        }
        return -1;
*/

发表于 2021-08-18 10:02:55 回复(1)

夜寻极光。

JavaScript的：

function foundOnceNumber( arr ,  k ) {
    // write code here
    function pai(a,b){
        return a-b;
    }
    arr.sort(pai);
    for(let i =0;i<arr.length;i++){
        if(arr[i+1]!=arr[i]&&arr[i+1]!=arr[i+2]){
            return arr[i+1]
        }
    }
}

发表于 2021-08-06 13:56:35 回复(1)

牛客447641769号

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param arr int一维数组
# @param k int
# @return int
#
class Solution:
def foundOnceNumber(self , arr , k ):
# write code here
arr.sort()
i = len(arr)-1
while i :
print(i)
if arr[i] == arr[i-1]:
i = i - k
else:
return arr[i]

发表于 2021-07-23 21:36:07 回复(0)

cqu后起之秀

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr intvector 
     * @param k int 
     * @return int
     */
    int foundOnceNumber(vector<int>& arr, int k) {
        // write code here
        sort(arr.begin(),arr.end());
        int i = 1;
        for (; i < arr.size() - 1; i += k - 1) {
            if (arr[i - 1] != arr[i] && arr[i] != arr[i + 1]) {
                return arr[i];
            }
        }
        return arr[arr.size() - 1];
    }
};

发表于 2021-07-13 17:21:28 回复(0)

Java

╰☆╮南巷雨落♡

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr int一维数组 
     * @param k int 
     * @return int
     */
    public int foundOnceNumber (int[] arr, int k) {
        for(int i=0;i<arr.length;i++){
            int count=0;
            for(int j=0;j<arr.length;j++){
                if(arr[i]==arr[j]){
                    count++;
                }
            }
            if(count==1){
                return arr[i];
            }
        }
        return -1;
    }
}

发表于 2021-06-18 16:30:31 回复(2)

Java

惠灵顿靖

//暴力破解
import java.util.*;
public class Solution {
    public int foundOnceNumber (int[] arr, int k) {
        // write code here
        for(int i=0;i<arr.length;i++)
        {int count=0;
            for(int j=0;j<arr.length;j++)
            {
                if (arr[i]==arr[j])
                    count++;
            }
         if(count==1)
         {
             return arr[i];
         }
        }
        return -1;
    }
}

发表于 2021-04-02 14:38:34 回复(1)

牛牛过劳模饿

将数组排序，如果遍历到该元素和左边还有右边的元素都不一样，返回该元素，注意临界条件，该元素可能在末尾，需要单独返回最后一个元素

public int foundOnceNumber (int[] arr, int k) {

        // write code here
         Arrays.sort(arr);
          for(int i=1;i<arr.length-1;i++){

             if(arr[i]!=arr[i-1]&&arr[i]!=arr[i+1]){
                   return arr[i];
             }
         }

        return arr[arr.length-1];
    }

发表于 2021-04-01 17:05:47 回复(2)

C++

creama

哈希表比较简单，统计就行了。

位运算有点技巧，统计arr中每个元素在32位int数据类型每个位上的和，如果这个位的和正好是k的倍数，那么只出现一次的那个数在这位的值为0，因为其他出现k次的数在这一位的和加起来刚好被k整除；否则只出现一次的那个数在这位的值为1。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr intvector 
     * @param k int 
     * @return int
     */
    int foundOnceNumber(vector<int>& arr, int k) {
        // write code here
        //哈希表
//         unordered_map<int, int> unmap;
//         for(auto a : arr){
//             unmap[a]++;
//         }
//         for(auto m : unmap){
//             if(m.second == 1){
//                 return m.first;
//             }
//         }
//         return -1;
        
        //位运算
        int res = 0;
        for(int i = 0; i < 32; i++){
            int count = 0;
            for(auto a : arr){
                if(a&(1<<i)) ++count;
            }
            if(count % k == 1) res ^= (1 << i);
        }
        return res;
    }
};

发表于 2021-07-25 23:14:41 回复(0)

JavaScript

别卷啦！

遍历数组里面的数的每个比特位，然后将32位比特位中不能被k整除的1，依次还原，最终得到所需数字。

function foundOnceNumber( arr ,  k ) {
    // write code here
   //计算每一位上出现1的个数，%k得到出现一次的数
    let res = 0;
    for(let i=0;i<32;++i){
        let sum =0;
        for(let num of arr){
            //用无符号右移，防止正负号的影响
            //依次右移num，同1相与，计算每一位上1的个数
            sum+=(num>>i)&1
        }
        //对sum取余，左移恢复
        res^=(sum%k)<<i
    }
    return res
}

编辑于 2021-01-15 16:38:43 回复(4)

wengJJ

非常巧妙的方法，自己记录一下

例子：3，3，3，2(k=3)

3：011

2：010

t: 043

t%3

r: 010 = 2

发表于 2021-06-07 23:07:06 回复(1)

牛客840486262号

class Solution:
    def foundOnceNumber(self , arr , k ):
        arr.sort()
        for i in range(0,len(arr)-1,k):
            if arr[i]==arr[i+1]:
                i+=k-1
            else:
                return arr[i]
        return arr[len(arr)-1]

发表于 2021-06-29 13:58:59 回复(0)

俞帅宝

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr intvector 
     * @param k int 
     * @return int
     */
    int foundOnceNumber(vector<int>& arr, int k) {
        // write code here
        //哈希表解法
        unordered_map<int,int>map_;
        sort(arr.begin(),arr.end());
        for(int i=0;i<arr.size();i++)
        {
            map_[arr[i]]++;
        }
        for(auto[a,b]:map_)
            if(b==1)return a;
        return 0;

    }
};

发表于 2021-06-24 09:43:38 回复(1)

牛客251657820号

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr intvector 
     * @param k int 
     * @return int
     */
    int foundOnceNumber(vector<int>& arr, int k) {
        // 思路
        // 统计每一位上1出现的次数，然后模k，剩下的余数就是只出现一次的数的对于的位
        vector<int> cnt(32, 0);
        for(auto num : arr)
        {
            for(int i = 0; i < 32; ++i)
            {
                int mask = 1 << i;
                if(num & mask)
                {
                    cnt[i]++;
                }

            }
        }

        int ans = 0;
        for(int i = 0; i < 32; ++i)
        {
            if(cnt[i]%k)
            {
                ans |= (1 << i);
            }
        }

        return ans;
    }
};

发表于 2023-04-03 12:49:57 回复(0)

Newman1997

看到数组的题，往往排序之后做回简单很多！

由于k>1，所以排序后除了我们的目标，其他数肯定不是前边有相同的就是后边有相同的，利用这一点轻松找出目标数。

function foundOnceNumber( arr ,  k ) {
    arr.sort()
    for(let i=0;i<arr.length;i++){
        if(arr[i]!=arr[i-1] && arr[i]!=arr[i+1]) return arr[i]
    }
}

发表于 2021-03-27 22:03:54 回复(0)

C++

感谢靓仔赏饭吃

#include <unordered_map>
class Solution {
  public:
     int foundOnceNumber(vector<int>& arr, int k) {
        unordered_map<int, int>hash;
        int ans;
        for (int i = 0; i < arr.size(); i++) {
            hash[arr[i]]++;
        }
        for ( auto i : hash) {
            if (i.second == 1) {
                ans = i.first;
            }
        }
        return ans;
    }
};

发表于 2024-04-12 17:50:49 回复(0)

Java

牛客839384289号

    public int foundOnceNumber (int[] arr, int k) {
        // write code here
        int[] binary=new int[32];
        for(int i=0;i<binary.length;i++){
            int sum=0;
            for(int num:arr){
                sum+=(num>>i)&1; //计算数据每个二进制位的1的加和
            }
            binary[i]=sum;
        }
        int res=0;
        for(int i=0;i<binary.length;i++){
            if(binary[i]%k!=0){ // 如果不能整除k，该位存在单数的二进制1，所有1左移加和
                res+=(1<<i);
            }
        }
        return res;
    }

编辑于 2024-03-24 16:48:40 回复(0)