题解 | #数组中只出现一次的数（其它数出现k次）#

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

http://www.nowcoder.com/practice/5d3d74c3bf7f4e368e03096bb8857871

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

问题描述：给定一个整型数组 $arr $和一个整数 $k(k>1)$k。已知 $arr$ 中只有 1 个数出现一次，其他的数都出现 $k$ 次。请返回只出现了 1 次的数。

示例

输入：[5,4,1,1,5,1,5],3

返回值：4

方法一

思路分析

本题我们很容易就能想到，先将整个数组进行排序，那么数组中存在的$k$个数就会连续放在一起，此时从数组开始元素处向后遍历，当相邻的两个元素相等时，那么这一子序列必然是$k$个相等的数，那么直接跳过这个$k$个数，继续下一次的比较，因为比较的位置只会在资格连续子序列的开始位置，如果相邻的元素不相等那么直接就可以找到只出现一次的数。

图解

输入：[5,4,1,1,5,1,5],3

首先对数组进行排序，得到[1,1,1,4,5,5,5]

相当于对数组进行了一次如下的划分

图解过程如下：

C++核心代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr intvector 
     * @param k int 
     * @return int
     */
    int foundOnceNumber(vector<int>& arr, int k) {
        // write code here
        int n=arr.size();
        sort(arr.begin(), arr.end());//对数组元素排序
        int ans=1;
        for(int i=0;i<n-1;i++)
        {
            if(arr[i]==arr[i+1])//如果存在两个元素相同,那么直接跳过这k-1个数进入下一次比较
                i+=k-1;//直接跳过这k-1个相等的数
            else
            {
                return arr[i];//一个数不属于一组k个数中，那么就找到了出现一次的数
            }
                
        }
        return arr[n-1];//单独的数在数组最后的位置
        
    }
};

复杂度分析

时间复杂度：首先需要对数组进行排序，时间复杂度为 $O(n\log n)$ ，一层循环遍历，里面有一次比较操作，因此时间复杂度为$O(n)$，因此总的时间复杂度为 $O(n\log n)$
空间复杂度: 空间复杂度为$O(1)$

方法二

思路分析

根据异或的思想：如果两个相同的数异或则结果为0 ，任何数与0 的异或是其本身，如果将整个数组所有元素相互异或，输出只有奇数个的元素，然后这种方法只适用于$k$为偶数的情况。因此使用位运算的办法，由于只有一个数出现一次，其余数出现$k$次，定义一个32维的数组，将数组中的所有元素按二进制数按位相加后存放在数组中，之后遍历32维的数组，对数组中每一位模$k$，模$k$如果有余数那么即为只出现一次的那个数的位，之后将取模后的数转换为二进制即可。

实例分析

首先将数组中的数转换为二进制后按位相加并存储在32维的数组中
之后对32维数组中的每一位模$k$，并将结果保存在该位中
对剩余的结果转换为十进制

输入：[5,4,1,1,5,1,5],3

转换为二进制：1的二进制为0001,4的二进制为0100,5的二进制为0101

之后按位相加存储在32维的数组中$bits[]=\{0,4,0,6\}$，之后对数组中的每一位模3，得到$bits[]=\{0,1,0,0\}$，将其转换为十进制即为4

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[] bits = new int[32];
        for (int i = 0; i < 32; i++)
        {
            for (int num : arr)
            {
                 bits[i] += (num >> i) & 1;//对数组元素中所有的数转换为二进制后按位相加
            }
            
           
        }
        int res = 0;
        for (int i = 0; i < 32; i++)
        {
            int num = bits[i];
            num %= k;//对32维的数组每一位模k，剩余的即为只出现一次的数的位
            res += num << i;//二进制数转换为十进制
        }
        return res;
    }
}