首页 > 代码库 > 数组中只出现一次的两个数字
数组中只出现一次的两个数字
题目：给定一个整型数组，其中有两个数字只出现一次，其余的数字都出现两次，找出这两个只出现一次的数字．时间复杂度为Ｏ(n)，空间复杂度为O(1)．
异或运算的特性：相等的两个整数异或的结果为０；一个整数与０进行异或运算的结果为其本身．
基本思想：将这两个只出现一次的数字分到两个数组中，这样就很容易找到只出现一次的数字．
采用上述思想需要解决的问题：
１．如何才能保证两个只出现一次的数字分别位于两个数组？
２．空间复杂度为Ｏ(1)，需要在原数组上进行分割操作，这个如何做到？
解决办法：
１．将数组中的所有数字进行异或运算，得到一个非零值．然后找出这个非零值的二进制形式中１第一次出现的位置．根据得到的这个位置的值是否为１将数组分成两个部分．可以得知，两个只出现一次的数字将被分到不同的部分．
２．快速排序的patition函数可以很好地解决这个问题．以某一标准将数组分成两个不同的部分．
代码如下：
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 void get_num(int *, int); 6 void swap(int *, int *); 7 8 int main(int argc, char *argv[]) 9 {10 int a[14] = {1, 2, 5, 1, 5, 2, 16, 20, 23, 20, 16, 30, 23, 6};11 int result = 0;12 13 get_num(a, sizeof(a)/sizeof(int));14 15 return 0;16 }17 18 void get_num(int *a, int len)19 {20 int result = 0;21 int result1 = 0;22 int result2 = 0;23 int m = 0;24 int i = 0;25 int j = 0;26 int p = 0;27 28 for (i=0; i<len; i++)29 {30 printf("%d ", *(a + i));31 result = *(a + i) ^ result;32 }33 printf("\n");34 35 while (m < 32)36 {37 if (result % 2 != 0)38 {39 break; 40 }41 42 result = result >> 1;43 m++;44 }45 printf("m = %d\n", m);46 i = -1;47 j = 0;48 for (j=0; j<len; j++)49 {50 if ((*(a + j) >> m) % 2 != 0)51 {52 swap((a + i + 1), (a + j));53 i++;54 }55 }56 57 p = i;58 for (i=0; i<=p; i++)59 {60 printf("%d ", *(a + i));61 result1 = *(a + i) ^ result1;62 }63 printf("\n");64 65 for (i=p+1; i<len; i++)66 {67 printf("%d ", *(a + i));68 result2 = *(a + i) ^ result2;69 }70 printf("\n");71 72 printf("%d %d\n", result1, result2);73 74 }75 76 77 void swap(int *a, int *b)78 {79 int temp;80 temp = *a;81 *a = *b;82 *b = temp;83 }
数组中只出现一次的两个数字
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。