Leetcode: SingleNumber II

Leetcode: SingleNumber II

题目：

Given an array of integers, every element appears three times except for one. Find that single one.

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

解答：（这是参照别人的答案一步步想通的）

方法一：

int 型数据共有32位，可以用32个变量存储 这n个元素中各个二进制位上1 出现的次数，最后在进行模3操作，如果为1，那说明这一位是要找元素二进制表示中为 1 的那一位。

int singleNumber(int A[], int n){ int bits[32] = {0};//一个整数32位 int result = 0;//记录结果 for (int i = 0; i < 32; i++) { for (int j = 0; j < n; j++) { //(A[j]>>i)&1的值为0或者1，表示第j个数字的第i位为0或者1 //将其结果相加便得到第i位为1的个数 bits[i] += (A[j]>>i)&1; } //将第i位的结果放到第i位上去 result |= (bits[i]%3)<

方法二：

利用3个变量分别保存各个二进制位上1出现1次、2次、3次的情况，最后只需返回出现1次的那个变量就行了。

int singleNumber(int A[], int n){ int one=0, two=0, three=0; for(int i = 0; i< n; i++){ two |= one & A[i]; one ^= A[i]; three = one & two; //每次将达到3的清零 one &= ~three; two &= ~three; } return one; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。