/
Lcof004.java
45 lines (41 loc) · 1.26 KB
/
Lcof004.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package com.gitee.passerr.leetcode.problem.lcof2.page1;
/**
* 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。
* 说明:
* <p>
* 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
* <p>
* 示例 1:
* 输入: [2,2,3,2]
* 输出: 3
* <p>
* 示例 2:
* 输入: [0,1,0,1,0,1,99]
* 输出: 99
* @author xiehai
* @date 2019/08/01 10:18
* @Copyright(c) tellyes tech. inc. co.,ltd
*/
public class Lcof004 {
// #region snippet
public int singleNumber(int[] nums) {
int result = 0;
// 从第31位开始 符号位也要判断
for (int i = 31; i >= 0; i--) {
int cnt = 0, bit = 1 << i;
for (int num : nums) {
// 来判断位元是否为0 若存在符号位 结果为负数
if ((bit & num) != 0) {
cnt++;
}
}
// 计算int所有为中1出现的次数 对3取余 剩余的就是只出现了一次的数字
if (cnt % 3 != 0) {
// 数字累加
result |= bit;
}
}
return result;
}
// #endregion snippet
}