1.只出现一次的数(136 – 易)
题目描述:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 :
输入: [2,2,1]
输出: 1
输入: [4,1,2,1,2]
输出: 4
思路:
法1:本题比较常规的解法是用集合进行记录,最终返回集合中的唯一元素,代码实现如下,但这里空间复杂度O(n)!
法2:先排序后比较有没有落单的,落单返回,时间复杂度O(nlogn),空间复杂度O(1)。
法3:根据异或对象相同为0,不同为1的规则,可以推导出一些性质
- 0 ⊕ a = a
- a ⊕ a = 0
此外,异或满足交换律以及结合律。
代码实现:
解法1:
public int singleNumber(int[] nums) {
HashSet set = new HashSet();
for (int i = 0; i
ps:这里注意迭代器和数据结构中的链表一样,有个header指针,header->next()就是链表中第一个元素…… 如下所示:
pre 1 2 3 4
开始header指针指向pre,当执行一次iterator().next()就是返回指针所指的元素,即返回1,本题中返回那个唯一元素。
解法2:
public int singleNumber(int[] nums) {
if (nums.length == 1) return nums[0];
int i = 1;
Arrays.sort(nums);
for ( ; i
解法3:
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i
2.只出现一次的数(137 – 中)
题目描述:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 :
输入: [2,2,3,2]
输出: 3
输入: [0,1,0,1,0,1,99]
输出: 99
思路:
法1:和1不同的是,本题重复数字变成3个,可以用HashMap来实现计数,但时间复杂度O(n);
法2:和案例1解法2思路相同,先排序,后比较;
法3:参考 这里 的一个解法。我们把数字放眼到二进制形式。
假如例子是 1 2 6 1 1 2 2 3 3 3, 3 个 1, 3 个 2, 3 个 3,1 个 6
1 0 0 1
2 0 1 0
6 1 1 0
1 0 0 1
1 0 0 1
2 0 1 0
2 0 1 0
3 0 1 1
3 0 1 1
3 0 1 1
看最右边的一列 1001100111 有 6 个 1
再往前看一列 0110011111 有 7 个 1
再往前看一列 0010000 有 1 个 1
我们只需要把是 3 的倍数的对应列写 0,不是 3 的倍数的对应列写 1
也就是 1 1 0,也就是 6。
原因的话,其实很容易想明白。如果所有数字都出现了 3
次,那么每一列的 1
的个数就一定是 3
的倍数。之所以有的列不是 3
的倍数,就是因为只出现了 1
次的数多贡献出了 1
。
所以所有不是 3
的倍数的列写 1
(多出的数有贡献),其他列写 0
(无贡献) ,就找到了这个出现 1
次的数。
本解法也可以进行推广,即是n
的倍数列写1
,其他列写0
,找到其余元素都出现n
次时,出现1
次的元素。
代码实现:
解法1:
public int singleNumber(int[] nums) {
HashMap map = new HashMap();
for (int i = 0; i
解答2:
public int singleNumber(int[] nums) {
if (nums.length == 1) return nums[0];
int i = 2;
Arrays.sort(nums);
for (i = 2; i
解法3:外层循环32位二进制,可以认为时间复杂度为O(n)
public int singleNumber(int[] nums) {
int ans = 0;
//考虑每一位
for (int i = 0; i >> i & 1) == 1) {
count++;
}
}
//1
ps:注意先位运算再进行逻辑运算。java优先级口诀:单目乘除为(位)关系,逻辑三目后赋值。
- 单目:单目运算符+ –(负数) ++ — 等
- 乘除:算数单目运算符* / % + –
- 为:位移单目运算符> >>>
- 带符号右移>>(相当于除以2):正数右移高位补0,负数右移高位补1。
- 无符号右移>>>:无论正数负数,高位统统补0。
- 关系:关系单目运算符> =
- 逻辑:逻辑单目运算符&& || & | ^
- 三目:三目单目运算符A > B ? X : Y
- 后:无意义,仅仅为了凑字数
- 赋值:赋值 =