当前位置:   article > 正文

40-找数组中只出现奇数次的n个数字(n=1,2)_数组中只有两个奇数

数组中只有两个奇数

一、题目描述

题目一:一个整型数组里除了1个数字之外,其他的数字都出现了偶数次,找出这个数字,要求时间复杂度O(n),空间复杂度O(1)
题目二:一个整型数组里除了2个数字之外,其他的数字都出现了偶数次,找出这两个数字,要求时间复杂度O(n),空间复杂度O(1)

二、解题思路

题目一:异或运算,偶数个一样的数异或为0,异或符合交换律,所以只需要把所有数组中所有数字异或一次就可以了
题目二:整体做异或运算,结果必不为0,且结果数字的二进制表示中至少有一位为1,找出第一个为1的位置target_index,以其为标准将原数组分为两个子数组,第一个子数组中每个数字的第target_index位置上的都是1,第二个子数组中每个数字的第target_index位置上的都是0。那么每个子数组中分别包含一个出现奇数次的数字,分别做异或即可

三、解题算法

1、题目一:找出现奇数次的一个数字

  1. /******************************************************
  2. author:tmw
  3. date:2018-8-7
  4. ******************************************************/
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <stdbool.h>
  8. /** 题目一
  9. * 只有一个数字出现奇数次
  10. **/
  11. void findNumber1AppearOdd(int* array, int array_len)
  12. {
  13. /**入参检查**/
  14. if( !array || array_len < 2 ) return;
  15. int res = 0;
  16. int i;
  17. for( i=0; i<array_len; i++ )
  18. res = res ^ array[i];
  19. printf("%d\n",res);
  20. }

2、题目二:找出现奇数次的两个数字

  1. /******************************************************
  2. author:tmw
  3. date:2018-8-7
  4. ******************************************************/
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <stdbool.h>
  8. /**判断当前数字第target_index位是否为1**/
  9. bool isBit1( int number, int target_index )
  10. {
  11. number = number >> target_index;
  12. return number&1;
  13. }
  14. /**有两个数字出现奇数次**/
  15. void findNumbers2AppearOdd(int *array, int array_len)
  16. {
  17. if( array == NULL || array_len < 2 ) return;
  18. /**对整体做异或,得到不为0的值**/
  19. int excusiveOR_res = 0;
  20. int i;
  21. for( i=0; i<array_len; i++ )
  22. excusiveOR_res = excusiveOR_res^array[i];
  23. /**找到excusiveOR_res中第一个为1的位置**/
  24. int target_index = 0;
  25. while( excusiveOR_res & 1 == 1 && target_index < 8*sizeof(int) )
  26. {
  27. /**右移1位**/
  28. excusiveOR_res = excusiveOR_res >> 1;
  29. target_index++;
  30. }
  31. /**按照target_index位置上的值是否为1,将数组分成两个部分计算,分别得到结果**/
  32. int res1 = 0;
  33. int res2 = 0;
  34. for( i=0; i<array_len; i++ )
  35. {
  36. if( isBit1(array[i], target_index) )
  37. res1 = res1 ^ array[i];
  38. else
  39. res2 = res2 ^ array[i];
  40. }
  41. printf("res1 = %d",res1);
  42. printf("res2 = %d",res2);
  43. }

 

                                                                                                          梦想还是要有的,万一实现了呢~~~~~ヾ(◍°∇°◍)ノ゙~~~~~~~

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/602423
推荐阅读
相关标签
  

闽ICP备14008679号