首页 > 代码库 > 75 int类型数组中除了一个数出现一次或两次以外,其他数都出现三次,求这个数。
75 int类型数组中除了一个数出现一次或两次以外,其他数都出现三次,求这个数。
【本文链接】
http://www.cnblogs.com/hellogiser/p/single-number-of-array-with-other-three-times.html
【题目】
int类型数组中除了一个数出现一次或两次以外,其他数都出现三次,求这个数。
【分析】
C++ Code
1 2 3 4 5 6 7 8 9 10 11 12 | int singleNumber(int *a, int n) { int ones = 0, twos = 0; for (int i = 0; i < n; i++) { ones = (ones ^ a[i]) & (~twos); twos = (twos ^ a[i]) & (~ones); } // ones return ones; } |
当a出现一次的时候,ones能保存a。当a出现两次的时候,twos能保存a。当a出现三次的时候,ones和twos都清零。所以,如果一个数值中所有的数都通过这个循环的话,出现三次的数都清零了,有一个数如果出现一次,它保存在ones中;如果出现两次的话保存在twos中。
【代码】
C++ Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | // 75_OneTwoNumber_WithOther3Times.cpp : Defines the entry point for the console application. // /* version: 1.0 author: hellogiser blog: http://www.cnblogs.com/hellogiser date: 2014/9/18 */ #include "stdafx.h" #include "iostream" using namespace std; void print(int *a, int n) { for (int i = 0; i < n; i++) { cout << a[i] << " "; } cout << endl; } //============================================================== // single number 1,1,1,2========>2 //============================================================== /* x 1st, ones =x, twos =0 x 2st, ones =0, twos =x x 3st, ones =0, twos =0 */ int singleNumber(int *a, int n) { int ones = 0, twos = 0; for (int i = 0; i < n; i++) { ones = (ones ^ a[i]) & (~twos); twos = (twos ^ a[i]) & (~ones); } // ones return ones; } //============================================================== // double number 1,1,1,100,100========>100 //============================================================== int doubleNumber(int *a, int n) { int ones = 0, twos = 0; for (int i = 0; i < n; i++) { ones = (ones ^ a[i]) & (~twos); twos = (twos ^ a[i]) & (~ones); } // twos return twos; } void test_base_single() { int a[] = {1, 1, 1, 2}; int n = 4; cout << "array is: "; print(a, n); cout << "single number " << singleNumber(a, n) << endl; } void test_base_double() { int a[] = {1, 1, 1, 100, 100}; int n = 5; cout << "array is: "; print(a, n); cout << "double number " << doubleNumber(a, n) << endl; } void test_main() { test_base_single(); test_base_double(); } int _tmain(int argc, _TCHAR *argv[]) { test_main(); return 0; } /* array is: 1 1 1 2 single number 2 array is: 1 1 1 100 100 double number 100 */ |
75 int类型数组中除了一个数出现一次或两次以外,其他数都出现三次,求这个数。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。