剑指offer之面试题40数组中只出现一次的数字

Myth丶恋晨 2022-07-24 04:06 204阅读 0赞

问题描述：

一个整形数组里除了m个数字之外，其他数字都出现两次。找出这些出现一次的数字。要求时间复杂度为O(n)。

实现代码如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <limits.h>
    
    #define mask 0x1F
    #define BITSPERWORD 5
    
    void setBitMap(int *bitmap,int b){
    	bitmap[b>>BITSPERWORD]^=1<<(b&mask);
    }
    
    int compare(int *bitmap,int b){
    	return bitmap[b>>BITSPERWORD] & 1<<(b&mask);
    }
    void findNum(int *num,int len){
    	if(num==NULL || len<=0)return ;
    	int i,j=0;
    	int bitmap[1+len>>BITSPERWORD];
    	for(i=0;i<len;i++){
    		setBitMap(bitmap,num[i]);
    	}
    	for(i=0;i<len;i++){
    		if(compare(bitmap,num[i])>0){
    			printf("%d\t",num[i]);
    		}
    	}
    	
    }
    int main(int argc, char *argv[])
    {
    	int num[]={
    		1,1,2,2,3,3,4,5,6,6,7,8
    	};
    	int len = sizeof(num)/sizeof(int);
    	findNum(num,len);
    	
    	return 0;
    }

在这个算法中，我将剑指offer中的问题扩展了一下，使用bitmap来实现。

**参考资料**：  
剑指offer  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51384344  
作者：WSYW126

发表评论取消回复

表情：

评论列表（有 0 条评论，204人围观）

还没有评论，来说两句吧...

相关阅读

相关【剑指offer-Java版】40数组中只出现一次的数字

数组中只出现一次的数字：输入一个数组，该数组中有两个数字只出现了一次，其他数字都出现了两次，求出这两个只出现了一次的数字要求时间复杂度为O(n)空间复杂度为O(1) 考

旧城等待，/ 2022年08月21日 10:45/ 0 赞/ 147 阅读

相关剑指offer面试题求数组中只出现一次的数字

题目描述：一个整形数组里除了两个数字之外，其他的数字都出现了两次。例如输入\{2,4,3,6,3,2,5,5 \}，只有4、6这两个数字只出现了一次，其他数字都出现了两次，

浅浅的花香味﹌/ 2022年07月26日 01:29/ 0 赞/ 134 阅读

相关剑指offer之面试题40数组中只出现一次的数字

问题描述：一个整形数组里除了m个数字之外，其他数字都出现两次。找出这些出现一次的数字。要求时间复杂度为O(n)。实现代码如下： include <stdio.

Myth丶恋晨/ 2022年07月24日 04:06/ 0 赞/ 205 阅读

相关剑指Offer面试题40（Java版）：数组出现一次的数字

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。 \ 请些程序找出这两个只出现一次的数字。要求时间复杂度为O(n),空间复杂度为O(1) 例如输入数组

桃扇骨/ 2022年07月16日 04:52/ 0 赞/ 129 阅读

相关剑指offer 数组中只出现一次的数字

1.题目描述一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 2.分析之前做过找出数组中唯一一个只出现一次的数组，

傷城~/ 2022年06月15日 01:12/ 0 赞/ 152 阅读

相关剑指offer面试题[40]-数组中只出现一次的数字

题目描述一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。注意原题目要求空间复杂度为0(1)。位运算的具体思路可以参看

谁借莪１个温暖的怀抱￠/ 2022年06月12日 13:59/ 0 赞/ 178 阅读

相关剑指offer-题40：数组中只出现一次的数字

题目描述一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1) 实验平台：[牛客网

谁借莪１个温暖的怀抱￠/ 2022年05月27日 05:48/ 0 赞/ 169 阅读

相关剑指offer 数组中只出现一次的数字

题目描述一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。解题思路我们利用异或的特性，异或两个相同的数字的结果为零

偏执的太偏执、/ 2022年05月21日 05:18/ 0 赞/ 185 阅读

相关【剑指Offer】40数组中只出现一次的数字

题目描述一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。时间限制：1秒；空间限制：32768K；本题知识点：数组

r囧r小猫/ 2022年05月12日 13:58/ 0 赞/ 185 阅读

相关 40.数组中只出现一次的数字《剑指Offer》(Java版)

题目描述 > 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 / 一个整型数组里除了

淩亂°似流年/ 2022年01月30日 13:29/ 0 赞/ 175 阅读