Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
使用位操作异或,异或能使相同值得位数为0,这样两两相同的数都被抵消了。
public class Solution { //Time: O(n) Space: O(1) public int singleNumber(int[] A) { if (A == null || A.length == 0) { return -1; } int num = A[0]; for (int i = 1; i < A.length; i++) { num = num ^ A[i]; } return num; } }
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
可以用一个O(32)的数组来记录每个digit出现次数,最后对3求余。
也可以像Single Number I,利用二进制模仿三进制,用两个变量one, two,当两者都是1的时候说明出现3次,置0。
所以我们可以用二进制来模拟各种进制
public class Solution { //Time: O(n) Space: O(1) public int singleNumber(int[] A) { int one = 0; int two = 0; for (int i = 0; i < A.length; i++) { two = two | (one & A[i]); one ^= A[i]; int tmp = ~(one & two); one = tmp & one; two = tmp & two; } return one; } }
No comments:
Post a Comment