- 每日一题：LeetCode：540.有序数组中的单一元素
- 时间：2022-02-13
- 力扣难度：Medium
- 个人难度：Medium-
- 数据结构：数组
- 算法：哈希表、二分、位运算
2022-02-14：LeetCode：540.有序数组中的单一元素
1. 题目描述
题目：原题链接
- 给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
- 请你找出并返回只出现一次的那个数。
- 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
1 <= nums.length <= 10^50 <= nums[i] <= 10^5
输入输出规范
- 输入：有序数组
- 输出：单一元素
输入输出示例
- 输入：nums = [1,1,2,3,3,4,4,8,8]
- 输出：2
2. 方法一：二分
思路
- 本题要求出有序数组中的单一元素，由于其他元素都是成对的，所以本题如果使用线性的复杂度是非常容易的
- 方式一：因为数组有序，所以相等的元素一定相邻，遍历数组，判断相邻元素是否相等即可找到单一元素
- 方式二：遍历数组使用哈希表计数，然后找到计数为1的就是单一元素
- 由于是有序数组，数据具有二段性，可以通过二分来进行优化，将时间复杂度降低到对数级
- 二分的核心是确定左右指针变化时的条件，由于有序数组中相等元素一定相邻
- 所以在单一元素左侧，相邻的奇偶元素应该相等，即索引为 i 的元素应该满足
- i 是偶数：nums[i] == nums[i + 1]
- i 是奇数：nums[i] == nums[i - 1]
- 根据这一性质作为二分的判断条件，对奇偶索引位置分类讨论，不断缩小区间找到最终结果
- 本题要求出有序数组中的单一元素，由于其他元素都是成对的，所以本题如果使用线性的复杂度是非常容易的
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public int singleNonDuplicate(int[] nums) {
if(nums == null || nums.length == 0) return -1;
int left = 0, right = nums.length - 1;
int mid;
while(left < right) {
mid = (right - left) / 2 + left;
// mid为偶数：nums[mid] == nums[mid + 1]
if((mid & 1) == 0) {
if((mid + 1 < n && nums[mid] == nums[mid + 1]) {
left = mid + 1;
}else right = mid;
}else {
// mid为奇数：nums[mid] == nums[mid - 1]
if(mid - 1 > 0 && nums[mid] == nums[mid - 1]) {
left = mid + 1;
}else right = mid;
}
}
return nums[left];
}复杂度分析：n 是数组的大小
- 时间复杂度：$O(logn)$
- 空间复杂度：$O(1)$
3. 方法二：二分 & 异或位运算
思路
- 在方法一中，需要对奇偶性分类讨论，代码冗余
- 实际上，可以通过位运算中的异或运算符来统一两种情况
- i 为偶数：i ^ 1 == i + 1，结果为原来的偶数加一后的奇数
- i 为奇数：i ^ 1 == i - 1，结果为原来的奇数减一后的偶数
- 可以通过
mid ^ 1异或操作来统一奇偶时的情况，简化代码
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public int singleNonDuplicate(int[] nums) {
if(nums == null || nums.length == 0) return -1;
int left = 0, right = nums.length - 1;
int mid;
while(left < right) {
mid = (right - left) / 2 + left;
// mid为奇数：nums[mid] == nums[mid - 1]
// mid为偶数：nums[mid] == nums[mid + 1]
if(nums[mid] == nums[mid ^ 1]) {
left = mid + 1;
}else {
right = mid;
}
}
return nums[left];
}复杂度分析：n 是数组的大小
- 时间复杂度：$O(logn)$
- 空间复杂度：$O(1)$
4. 扩展：无序数组：位运算计数
-
- 当数组是无序数组时，因为数组无序，如果想要二分还需要先进行排序，得不偿失
- 此时同样可以使用哈希表，但是需要额外的$O(n)$空间
- 为了优化空间到常量级别，我们可以利用二进制数，因为 int 整型对应的二进制数最大为32位，我们可以维护一个长度位32的 bit 数组作为二进制位的计数数组
- 通过对每个数字对应的二进制数的每一个等于 1 的位进行计数，bit 数组实际上就是用来计数的数组，通过
(num >> i) & 1)移位运算符来逐个取当前元素的二进制位 - 因为无序数组中只有一个元素的单一元素，其他都是成对的，那么此时这个计数后的 bit 数组中由该单一元素贡献的部分(索引位置)的计数应为奇数
- 因此，就可以遍历计数数组 bit，找到计数个数是奇数的位，就可以通过这些位还原出该单一元素：
res += 1 << i - 注意：此时其他元素不一定都是两个，也可以是 k 个，此时只需要判断计数个数是否为 k 的倍数即可
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public int singleNonDuplicate(int[] nums) {
if(nums == null || nums.length == 0) return -1;
int[] bit = new int[32];
int res = 0;
int k = 2;
for(int num : nums) {
for(int i = 0; i < 32; i++) {
if(((num >> i) & 1) == 1) {
bit[i]++;
}
}
}
for(int i = 0; i < 32; i++) {
if(((bit[i] % k) & 1) == 1) {
res += 1 << i;
}
}
return res;
}复杂度分析：n 是数组的大小
- 时间复杂度：$O(32*n)$
- 空间复杂度：$O(32)$
本文作者：
Chthollists
发布时间： 2022-02-14 15:36:23
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:540.有序数组中的单一元素
本文链接： https://chthollists.github.io/post/2265e63b.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！
发布时间： 2022-02-14 15:36:23
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:540.有序数组中的单一元素
本文链接： https://chthollists.github.io/post/2265e63b.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！
