第 56-1 题：数组中只出现一次的两个数字
传送门：数组中只出现一次的两个数字，牛客网 online judge 地址。
一个整型数组里除了两个数字之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。
你可以假设这两个数字一定存在。
样例：
输入：
输出：
思路：按位分组。这道题有一定技巧性。
补充说明：^：按位异或运算符：当两对应的二进位相异时，结果为 ，可以记忆为“无符号加法”。
Python 代码：
class Solution(object):
def findNumsAppearOnce(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
l = len(nums)
if l < 2:
raise Exception('程序出错')
if l == 2:
return nums
# 全部相与一遍
xor = 0
for num in nums:
xor ^= num
# 最末尾的 1 从右向左边数在第几位
counter = 0
while xor & 1 == 0:
xor >>= 1
counter += 1
res = [0, 0]
for num in nums:
if (num >> counter) & 1 == 1:
res[1] ^= num
else:
res[0] ^= num
return res
Java 代码：
import java.util.Arrays;
// 第 56 题：数组中数字出现的次数 P275
// 参考资料：
// 1、https://blog.csdn.net/derrantcm/article/details/46771717
public class Solution {
// 考察位运算：或、与、异或、非，以及无符号左移 >>>
public int[] findNumbersAppearanceOnce(int[] nums) {
int len = nums.length;
int[] res = new int[2];
assert len >= 2;
if (len == 2) {
return nums;
}
// 那两个只出现一次的数的异或运算的结果
int xor = xor(nums);
// 关键在这里
// 找到这个 xor 的二进制表示第 1 个是 1 的数位是第几位
int binaryFirstNotZero = binaryFirstNotZero(xor);
// 接下来分别对两组进行异或
for (int i = 0; i < len; i++) {
// 如果这个数右移这么多位是 1 的分在一组，是 0 的分在另外一组，遍历的时候，就进行异或运算
if ((nums[i] >>> binaryFirstNotZero & 1) == 1) {
res[0] ^= nums[i];
} else {
res[1] ^= nums[i];
}
}
return res;
}
// 得到一个数组经过异或运算的结果 xor
// 异或 的英文翻译就是 xor
private int xor(int[] nums) {
int xor = 0;
for (int i = 0; i < nums.length; i++) {
xor ^= nums[i];
}
return xor;
}
// 得到一个整数的二进制表示从右到左第 1 个非零的位数是第几位
private int binaryFirstNotZero(int num) {
int index = 0;
// 这里的 1 把它看成二进制的 1，即 00000001
while ((num & 1) == 0 && index < 32) {
num >>>= 1;
index++;
}
// 走到这里满足 (num & 1) == 1
return index;
}
public static void main(String[] args) {
int[] nums = {2, 4, 3, 6, 3, 2, 5, 5};
Solution solution = new Solution();
int[] res = solution.findNumbersAppearanceOnce(nums);
System.out.println(Arrays.toString(res));
int[] nums2 = {2, 4, 3, 6, 3, 2, 5, 5};
int[] res2 = solution.findNumbersAppearanceOnce(nums2);
System.out.println(Arrays.toString(res2));
int[] nums3 = {4, 6};
int[] res3 = solution.findNumbersAppearanceOnce(nums3);
System.out.println(Arrays.toString(res3));
int[] nums4 = {4, 6, 1, 1, 1, 1};
int[] res4 = solution.findNumbersAppearanceOnce(nums4);
System.out.println(Arrays.toString(res4));
}
}
0 到 n-1 中缺失的数字
传送门：0 到 n-1 中缺失的数字。
一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0 到 n-1 之内。
在范围 0 到 n-1 的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。
样例
输入：[0,1,2,4] 输出：3
思路：典型的使用“二分法”解决的问题。
Python 代码：
class Solution(object):
def getMissingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
size = len(nums)
l = 0
r = size
while l < r:
mid = l + (r - l) // 2
if nums[mid] > mid:
# [0,1,2,3,4,6]
# mid 有可能是要求的数
r = mid
else:
assert nums[mid] <= mid
l = mid + 1
return l
if __name__ == '__main__':
solution = Solution()
nums = [0, 1, 2, 4]
result = solution.getMissingNumber(nums)
print(result)
数组中数值和下标相等的元素
传送门：数组中数值和下标相等的元素。
假设一个单调递增的数组里的每个元素都是整数并且是唯一的。
请编程实现一个函数找出数组中任意一个数值等于其下标的元素。
例如，在数组
中，数字
和它的下标相等。
样例：
输入：
输出：
注意：如果不存在，则返回
。
思路：典型的使用“二分法”解决的问题。
Python 代码：
class Solution(object):
def getNumberSameAsIndex(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 使用二分法
size = len(nums)
l = 0
r = size - 1
while l < r:
mid = l + (r - l) // 2
if nums[mid] < mid:
l = mid + 1
else:
assert nums[mid] >= mid
r = mid
return l if nums[l] == l else -1
第 56-2 题：数组中唯一只出现一次的数字
传送门：数组中唯一只出现一次的数字。
在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。
请找出那个只出现一次的数字。
你可以假设满足条件的数字一定存在。
思考题：
- 如果要求只使用
的时间和额外
的空间，该怎么做呢？
样例：
输入：[1,1,1,2,2,2,3,4,4,4] 输出：3
思路：限制在 空间复杂度，那就只有通过二进制，一位一位去看了。
Python 代码：
class Solution(object):
def findNumberAppearingOnce(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = 0
for i in range(32):
count = 0
for num in nums:
# 不要忘记 & 1
if (num >> i) & 1:
count += 1
if count % 3:
res += 1 << i
return res
if __name__ == '__main__':
nums = [1, 0, 0, 0, 2, 1, 1]
solution = Solution()
result = solution.findNumberAppearingOnce(nums)
print(result)
