leetcode:一度しか現れない数から異或を見る
最近leetcodeの上のプログラミングの問題をして、このような問題に出会った:1つの非空の整数の配列を与えて、ある要素が1回しか現れない以外、残りの要素はすべて2回現れます.それが一度しか現れなかった要素を見つけます.説明:あなたのアルゴリズムは線形時間の複雑さを持つべきです.余分なスペースを使わずに実現できますか?実際には,空間的複雑さを考慮しなければ,重複を許さないset集合のような他の配列構造を完全に利用することができ,ここでは詳細に議論しない.当時、長い間考えていたが、時間の複雑さと空間の複雑さを総合すると、なかなか良い解決策が見つからなかった.検索してみると、異或がこんなに簡単に使われていたことに気づきました.まずコードをつけます.
皆さんはよく知られていませんが、当時この問題を見たとき、問題の隠れた条件は見つかりませんでした.他の繰り返しの数字は2回しか現れませんでした.これは奇数と偶数の数字ではありませんか.これからは真剣に問題の意味を推測しなければなりません.では、なぜこの問題が異や解決できるのか見てみましょう.まず,異或はバイナリベースのビット演算であり,符号XORまたは^で表され,その演算アルゴリズムは演算子の両側数の各バイナリビットに対して同値0,異値1をとることを知っている.そして、この問題を分析するには、a XOR a=0、a XOR 0=a、a XOR 0=a、a XOR 0=a、a XOR 0=a、a XOR a、a XOR、a XOR、a XOR、a XOR、aこのように配列中の数字を一度に異ならせ、最終的に得られるのは奇数の数が現れるに違いない.一番応用されているのはこの法則だと思います.最後に2つの問題を添付して、一緒に練習しましょう.1.1-1000は、1001個の要素を含む配列に配置され、唯一の要素値のみが重複し、その他は1回のみ表示されます.各配列要素は一度しかアクセスできず、アルゴリズムを設計し、それを探し出すことができます.ストレージスペースを支援する必要がなく、アルゴリズムの実装を設計できますか?2.一つの配列はいくつかの整数を保存して、一つの数は奇数回現れて、残りの数はすべて偶数回現れて、この奇数回現れた数を探し出しますか?
public int singleNumber(int[] nums) {
int ret = 0;
int i = 0;
for( i = 0;i < nums.length;i++){
ret ^= nums[i];
}
return ret;
}
皆さんはよく知られていませんが、当時この問題を見たとき、問題の隠れた条件は見つかりませんでした.他の繰り返しの数字は2回しか現れませんでした.これは奇数と偶数の数字ではありませんか.これからは真剣に問題の意味を推測しなければなりません.では、なぜこの問題が異や解決できるのか見てみましょう.まず,異或はバイナリベースのビット演算であり,符号XORまたは^で表され,その演算アルゴリズムは演算子の両側数の各バイナリビットに対して同値0,異値1をとることを知っている.そして、この問題を分析するには、a XOR a=0、a XOR 0=a、a XOR 0=a、a XOR 0=a、a XOR 0=a、a XOR a、a XOR、a XOR、a XOR、a XOR、aこのように配列中の数字を一度に異ならせ、最終的に得られるのは奇数の数が現れるに違いない.一番応用されているのはこの法則だと思います.最後に2つの問題を添付して、一緒に練習しましょう.1.1-1000は、1001個の要素を含む配列に配置され、唯一の要素値のみが重複し、その他は1回のみ表示されます.各配列要素は一度しかアクセスできず、アルゴリズムを設計し、それを探し出すことができます.ストレージスペースを支援する必要がなく、アルゴリズムの実装を設計できますか?2.一つの配列はいくつかの整数を保存して、一つの数は奇数回現れて、残りの数はすべて偶数回現れて、この奇数回現れた数を探し出しますか?