首页 > 试题广场 >

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

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

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

输出

算法知识视频讲解

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)

Java

益塘

import java.util.*;


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

             }   
            return arr[i];
        
    }
}

发表于 2022-04-14 18:15:40 回复(0)

Java

为她

先将数组排序，每次设置两个指针，每次都将指针后移k个单位

public int foundOnceNumber (int[] arr, int k) {       
     Arrays.sort(arr);
    int left = 0;
    int right = k - 1;    
    while(right < arr.length && arr[left] == arr[right]){//循环结束的条件
      left = right + 1;
      right += k;
    }    
    return arr[left];//此时left刚好是答案
    }
}

发表于 2022-03-10 09:18:06 回复(0)

Java

FriskKiddo

    public int foundOnceNumber (int[] arr, int k) {
        // write code here
        //所有int型数字bit位之和
        int[] binSum = new int[32];
        
        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];
            for (int j = 0; j < 32; j++) {
                binSum[j] += ((num >> j) & 1);
            }
        }
        int ans = 0;
        //binSum[i] % k 得到出现一次数在第i bit位的值
        for (int i = 0; i < 32; i++) {
            ans += ((binSum[i] % k) << i);
        }
        
        return ans;
    }

发表于 2022-02-22 16:32:00 回复(0)

Java

许你清安L

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr int一维数组 
     * @param k int 
     * @return int
     */
    public int foundOnceNumber (int[] arr, int k) {
        // write code here
        if(k % 2 == 0){
            return find(arr);
        }
//         奇偶k都可以解决
//         因为其他的数都出现了k次 意味着在某一位二进制的位上的1/0出现了 nk 次
//         在考虑只出现一次的答案 他在这个位置的 0 1会叠加上去
//         以下只考虑某位1的数目（0的也是如此）
//         非答案的某一位 1的个数 必然是 nk
//         加上答案的某一位 1的个数 就是 nk + 1 或者 nk(答案此位为 0)
//         可以发现答案的某一位是0还是1 等于 某一位1的个数取模k
//         因此我们可以遍历统计每一位上的1的个数 然后取模获得 最终结果的某位
        int res = 0;
        for(int i = 0; i < 32; i++){
            int total = 0;
            for(int num : arr){
                total += (num >> i) & 1;
            }
            
            res |= (total % k ) << i;
        }
        return res;
    }
    
    private int find(int[] nums){
        int res = 0;
        for(int num:nums){
            res ^= num;
        }
        return res;
    }
}

发表于 2021-12-09 13:20:23 回复(0)

Java

合肥吴彦祖

public int foundOnceNumber (int[] arr, int k) {
        // write code here
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int num : arr){
            map.put(num, map.getOrDefault(num,0) +1);
        }
        
        for(Integer i : map.keySet()){
            if(map.get(i) == 1) return i;
        }
        return 0;
    }

发表于 2021-12-03 19:01:48 回复(0)

Java

Padavan

    public int foundOnceNumber (int[] arr, int k) {
        //首先进行排序
        Arrays.sort(arr);
        for(int i=0;i<=arr.length-2;i=i+k){//步长为i+k;
            if(arr[i] != arr[i+1]){//只要是不重复的，那么和相邻（和右边的数进行比较）的两个数一定不相等
                return arr[i];
            }
        }
        return arr[arr.length-1];//如果到倒数第二个数都没有找到，说明最后一个数就是不重复的那个数
            
}

发表于 2021-10-18 20:10:01 回复(0)

Java

向小牛牛学习吃嘛嘛香

public class Solution {
    public int foundOnceNumber (int[] arr, int k) {
        int ans = 0;
        for(int i = 0; i < 32; i++){
            int sum = 0;
            for(int j = 0; j < arr.length; j++){
                sum += (arr[j] >> i) & 1;
            }
            ans |= (sum % k) << i;
        }
        return ans;
    }
}

发表于 2021-10-12 14:05:27 回复(0)

Java

jarsing

虽然是个笨办法，但也不失为一种思路

import java.util.*;


public class Solution {
    public int foundOnceNumber (int[] arr, int k) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0;i<arr.length;i++) {
            if (map.containsKey(arr[i])) {
                map.put(arr[i], map.get(arr[i]) + 1);
            } else {
                map.put(arr[i], 1);
            }
        }

        for(Map.Entry<Integer, Integer> entry:map.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return -1;
    }
}

发表于 2021-10-08 23:03:29 回复(0)

Java

牛客774608432号

    public int foundOnceNumber (int[] arr, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < arr.length; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
        }
        
        Iterator it = map.keySet().iterator();
        while (it.hasNext()) {
            int key = (Integer)it.next();
            if (map.get(key) == 1) {
                return key;
            }
        }
        return -1;
    }

发表于 2021-10-04 18:27:16 回复(0)

Java

灬慕夜之华丶

import java.util.*;
 
public class Solution {
    public int foundOnceNumber (int[] arr, int k) {
        int[] countArr = new int [32];
        for(int num : arr){
            for(int i=0;i<32;i++){
                //32位int整型，计算每个位置上1的个数
                countArr[i] += (num>>(31-i))&1;
            }
        }
        int result = 0;
        for(int i=0;i<32;i++){
            //出现K次的数对应位置1的个数是K的倍数，否则就是目标数字
            result = (result<<1) + countArr[i]%k;
        }
        return result;
    }
}

发表于 2021-09-14 11:19:55 回复(0)

Java

超山望梅

public class Solution {
public int foundOnceNumber (int[] arr, int k) {
// write code here
//先冒泡排序
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
//独数在第一位
if(arr[0]!=arr[1]){
return arr[0];
}
//独数在最后一位
if(arr[arr.length-1]!=arr[arr.length-2]){
return arr[arr.length-1];
}
//独数在中间，前后都是异数
int jieguo=0;
for(int i=1;i<arr.length-1;i++){
if(arr[i]!=arr[i-1] && arr[i]!=arr[i+1]){
jieguo=arr[i];
break;
}
}
return jieguo;
}
}

发表于 2021-09-09 13:57:19 回复(0)

Java

牛气嘣嘣

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

奇数：

遍历进行异或，相同数值都会运算为0.最后结果就是ans

偶数：

定义HashMap
hashmap.put(arr[i],hashmap.getOrDefault(arr[i],0)+1);
循环得到Value为1的key值，返回结果

for(Map.Entry<Integer,Integer> entry:hashmap.entrySet()){
   if(entry.getValue()==1) return entry.getKey();
}

位运算：

public int foundOnceNumber (int[] arr, int k) {
    int ans = 0;
    for(int i = 0; i < 32; i++){
        int sum = 0;
        for(int a : arr){
            sum += (a >> i) & 1;
        }
        sum %= k;
        ans += (sum << i);
    }
    return ans;
}

发表于 2021-09-08 23:16:45 回复(0)

Java

岛。201904182324772

对数组进行排序，连续出现的数字放在一起，控制i，发现相同的数字出现，挑过K个数字，再比较。
public int foundOnceNumber (int[] arr, int k) {
Arrays.sort(arr);
int i=0;
while(i<arr.length){
if(i==arr.length-1) return arr[i];
if(arr[i]==arr[i+1]){
i=i+k;
}
else{
return arr[i];
}
}
return 0;
}

发表于 2021-08-25 20:04:44 回复(0)

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)

Java

大厂我来了啊

位运算实在卷不懂

运行时间：66ms

超过41.88% 用Java提交的代码
占用内存：13800KB

超过58.19%用Java提交的代码

public int foundOnceNumber (int[] arr, int k) {
        // write code here
        Map<Integer,Integer> cache = new HashMap<>();
        for(int a : arr){
            int cnt = cache.getOrDefault(a,0) + 1;
            cache.put(a,cnt);
        }
        for(Map.Entry<Integer,Integer> entry : cache.entrySet()){
            if(entry.getValue() == 1){
                return entry.getKey();
            }
        }
        return -1;
    }

发表于 2021-07-14 16:37:42 回复(1)

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

AerCool

public int foundOnceNumber (int[] arr, int k) {
        // write code here
        //这个k其实没用额
        //先排序
        Arrays.sort(arr);
        //目标值
        int target = arr[0];
        //出现次数
        int t = 0;
        
        for(int x=0; x < arr.length; x++) {
            
            //如果相等，次数相加，继续下次循环
            if(arr[x] == target) {
                t ++;
                continue;
            }
            
            //如果不相等，则已经找完相等的数了，如果只有一，那我们就已经找到了
            if(arr[x] != target && t == 1) {
                return target;
            }
            
            //如果不相等，且上个数的次数大于1，则不是我们要的，跳过，赋值为当前值
            if(arr[x] != target && t > 1) {
                target = arr[x];
                t = 1;
            }  
        }
         return target;
    }

发表于 2021-05-12 23:27:34 回复(0)