Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

Commitffcfc40

Browse files
author
applewjg
committed
Single Number I && II
Change-Id: Iadeff09c004a9b330e715c0b3f9d9ccf72f98848
1 parent8054e5c commitffcfc40

File tree

2 files changed

+77
-0
lines changed

2 files changed

+77
-0
lines changed

‎SingleNumber.java

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Jan 3, 2015
4+
Problem: Single Number
5+
Difficulty: Easy
6+
Source: http://oj.leetcode.com/problems/single-number/
7+
Notes:
8+
Given an array of integers, every element appears twice except for one.
9+
Find that single one.
10+
Your algorithm should have a linear runtime complexity.
11+
Could you implement it without using extra memory?
12+
13+
Solution: XOR.
14+
*/
15+
publicclassSolution {
16+
publicintsingleNumber(int[]A) {
17+
intres =0;
18+
for (inti :A) {
19+
res =res^i;
20+
}
21+
returnres;
22+
}
23+
}

‎SingleNumberII.java

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Jan 3, 2015
4+
Problem: Single Number II
5+
Difficulty: Easy
6+
Source: http://oj.leetcode.com/problems/single-number-ii/
7+
Notes:
8+
Given an array of integers, every element appears three times except for one.
9+
Find that single one.
10+
Your algorithm should have a linear runtime complexity. Could you implement it
11+
without using extra memory?
12+
13+
Solution: 1. Count the number of each bit.
14+
2. We can improve this based on the previous solution using three bitmask variables.
15+
3. An excellent answer by @ranmocy in LeetCode Discuss:
16+
https://oj.leetcode.com/discuss/857/constant-space-solution?show=2542#a2542
17+
*/
18+
publicclassSolution {
19+
publicintsingleNumber_1(int[]A) {
20+
intres =0;
21+
for (inti =0;i <32; ++i) {
22+
intone =0;
23+
for (intnum :A) {
24+
if (((num >>i) &1) ==1) ++one;
25+
}
26+
res =res | ((one %3)<<i);
27+
}
28+
returnres;
29+
}
30+
publicintsingleNumber_2(int[]A) {
31+
intone =0,twice =0;
32+
for (intnum :A) {
33+
twice =twice | (one &num);
34+
one =one ^num;
35+
intthree =one &twice;
36+
one =one ^three;
37+
twice =twice ^three;
38+
}
39+
returnone;
40+
}
41+
publicintsingleNumber(int[]A) {
42+
intk =1,n =3;
43+
int[]x =newint[n];
44+
x[0] = ~0;
45+
for (intnum :A) {
46+
intt =x[n-1];
47+
for (inti =n -1;i >=1; --i) {
48+
x[i] = (x[i-1] &num) | (x[i] & ~num);
49+
}
50+
x[0] = (t &num) | (x[0] & ~num);
51+
}
52+
returnx[k];
53+
}
54+
}

0 commit comments

Comments
 (0)

[8]ページ先頭

©2009-2025 Movatter.jp