LeetCode——Single Number II
776 ワード
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?
整数配列が与えられ、1つを除いて他の各要素が3回現れ、それを見つけます.
前の問題のハッシュテーブルを利用した解法を完全に適用することができる.
もう1つの解法は、変数onesでバイナリ1が1回しか現れない数位を表し、twosでバイナリ1が2回しか現れない数位を表し、threesでバイナリ1が3回現れる数位を表す.onesとtwosのいずれかが同時に1である場合はバイナリ1が3回現れることを示し,この場合はクリアが必要である.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
整数配列が与えられ、1つを除いて他の各要素が3回現れ、それを見つけます.
前の問題のハッシュテーブルを利用した解法を完全に適用することができる.
もう1つの解法は、変数onesでバイナリ1が1回しか現れない数位を表し、twosでバイナリ1が2回しか現れない数位を表し、threesでバイナリ1が3回現れる数位を表す.onesとtwosのいずれかが同時に1である場合はバイナリ1が3回現れることを示し,この場合はクリアが必要である.
public int singleNumber(int[] A) {
int ones = 0, twos = 0;
for (int i = 0; i < A.length; i++) {
twos = twos | (ones & A[i]);
ones = ones ^ A[i];
// 3 0,
int threes = ~(ones & twos);
ones &= threes;
twos &= threes;
}
return ones;
}