赞
踩
题目一:一个整型数组里除了1个数字之外,其他的数字都出现了偶数次,找出这个数字,要求时间复杂度O(n),空间复杂度O(1)
题目二:一个整型数组里除了2个数字之外,其他的数字都出现了偶数次,找出这两个数字,要求时间复杂度O(n),空间复杂度O(1)
题目一:异或运算,偶数个一样的数异或为0,异或符合交换律,所以只需要把所有数组中所有数字异或一次就可以了
题目二:整体做异或运算,结果必不为0,且结果数字的二进制表示中至少有一位为1,找出第一个为1的位置target_index,以其为标准将原数组分为两个子数组,第一个子数组中每个数字的第target_index位置上的都是1,第二个子数组中每个数字的第target_index位置上的都是0。那么每个子数组中分别包含一个出现奇数次的数字,分别做异或即可
- /******************************************************
- author:tmw
- date:2018-8-7
- ******************************************************/
- #include <stdio.h>
- #include <stdlib.h>
- #include <stdbool.h>
-
- /** 题目一
- * 只有一个数字出现奇数次
- **/
- void findNumber1AppearOdd(int* array, int array_len)
- {
- /**入参检查**/
- if( !array || array_len < 2 ) return;
-
- int res = 0;
- int i;
- for( i=0; i<array_len; i++ )
- res = res ^ array[i];
- printf("%d\n",res);
- }
- /******************************************************
- author:tmw
- date:2018-8-7
- ******************************************************/
- #include <stdio.h>
- #include <stdlib.h>
- #include <stdbool.h>
-
- /**判断当前数字第target_index位是否为1**/
- bool isBit1( int number, int target_index )
- {
- number = number >> target_index;
- return number&1;
- }
- /**有两个数字出现奇数次**/
- void findNumbers2AppearOdd(int *array, int array_len)
- {
- if( array == NULL || array_len < 2 ) return;
-
- /**对整体做异或,得到不为0的值**/
- int excusiveOR_res = 0;
- int i;
- for( i=0; i<array_len; i++ )
- excusiveOR_res = excusiveOR_res^array[i];
-
- /**找到excusiveOR_res中第一个为1的位置**/
- int target_index = 0;
- while( excusiveOR_res & 1 == 1 && target_index < 8*sizeof(int) )
- {
- /**右移1位**/
- excusiveOR_res = excusiveOR_res >> 1;
- target_index++;
- }
-
- /**按照target_index位置上的值是否为1,将数组分成两个部分计算,分别得到结果**/
- int res1 = 0;
- int res2 = 0;
- for( i=0; i<array_len; i++ )
- {
- if( isBit1(array[i], target_index) )
- res1 = res1 ^ array[i];
- else
- res2 = res2 ^ array[i];
- }
- printf("res1 = %d",res1);
- printf("res2 = %d",res2);
- }
梦想还是要有的,万一实现了呢~~~~~ヾ(◍°∇°◍)ノ゙~~~~~~~
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。