本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
268. 缺失数字
本题来自 LeetCode：268. 缺失数字[1]
题目描述
给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
示例 1:
输入: [3,0,1]
输出: 2
示例 2:
输入: [9,6,4,2,3,5,7,0,1]
输出: 8
说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
解法一
题目分析
本题的题意是从
0...n这
n + 1个数字中，选取
n个数，要找到其中缺失的那个数。
题目解答
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
// 记录
int indexN = -1;
for(int i = 0; i n; i ++) {
// 将除n以外的数放到正确的位置上
while(nums[i] != n && nums[i] != i) {
swap(nums, nums[i], i);
}
// 记录n的位置
if(nums[i] == n) {
indexN = i;
}
}
// 若没有找到n则缺少n，若找到了n，则n元素所处的位置就是缺失的数
return indexN == -1 ? n : indexN;
}
public void swap(int[] nums ,int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
解法二
题目分析
本题也可以采用位运算异或来解答。由于
i ^ i = 0，故可以将
0...n这
n个数进行异或运算，然后再和数组
nums中的所有数组进行异或运算，最后剩下的数就是缺失的数。
题目解答
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int missing = n;
for(int i = 0; i n; i ++) {
missing = missing ^ i ^ nums[i];
}
return missing;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
136. 只出现一次的数字
本题来自 LeetCode：136. 只出现一次的数字[2]
题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
题目分析
本题可以采用位运算异或来解答。由于
i ^ i = 0，除了某个元素只出现一次以外，其余每个元素均出现两次，故将数组
nums中的所有数组进行异或运算，最后剩下的数就是只出现一次的数。
题目解答
class Solution {
public int singleNumber(int[] nums) {
int single = 0;
for(int i = 0; i nums.length; i ++) {
single = single ^ nums[i];
}
return single;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
参考资料
原文始发于微信公众号（xiaogan的技术博客）：
