《leetCode》：Single Number II

本文主要是介绍《leetCode》：Single Number II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

Given an array of integers, every element appears three times except for one. Find that single one.Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

思路一

由于在数组中除了一个数之外的其它数都出现3次，则对于每个数的32个bit位来看，每个bit位出现的1的次数模3，我们所要求的数在该bit位的值就是此余数。也就是说：
int 数据共有32位，可以用32变量存储 这 N 个元素中各个二进制位上 1 出现的次数，最后 在进行 模三 操作，如果为1，那说明这一位是要找元素二进制表示中为 1 的那一位。时间复杂度为：O(32n)，空间复杂度为O(32)
这个算法是一个通用的算法，如果把出现3次改为 k 次，那么只需模k就行了

实现代码如下：

/*
所有数均出现3次，除了一个只出现一次
*/
#define N_Bit 32
int singleNumber(int* nums, int numsSize) {if(nums==NULL||numsSize<1){return 0;}int *bitNum=(int *)malloc(N_Bit*sizeof(int));if(bitNum==NULL){exit(EXIT_FAILURE);}memset(bitNum,0,N_Bit*sizeof(int));for(int i=0;i<numsSize;i++){int value=nums[i];for(int j=0;j<N_Bit;j++){bitNum[j]+=(value&1);value=(value>>1);}}int res=0;for(int i=0;i<N_Bit;i++){bitNum[i]=bitNum[i]%3;res|=(bitNum[i]<<i);}return res; 
}

这篇关于《leetCode》：Single Number II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---