LeetCode算法题-Missing Number(Java实现-四种解法)
这是悦乐书的第200次更新,第209篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第65题(顺位题号是268)。给定一个包含n个不同数字的数组,取自0,1,2,…,n,找到数组中缺少的数字。例如:
输入:[3,0,1]
输出:2
输入:[9,6,4,2,3,5,7,0,1]
输出:8
注意:您的算法应该以线性运行时复杂性运行。 你能用恒定的额外空间复杂度来实现吗?
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
特殊情况:当nums为null的时候,或者nums中没有元素的时候,直接返回0即可。
正常情况:缺失的数字分为三种情况:一是缺失的数字在中间,比如{0,1,2,4},此时缺失的数字是3;二是缺失的数字在末尾,比如{0,1,2,3},此时缺失的数字就是4;三是缺失的数字在头部,比如{1,2,3,4},此时缺失的数字就是0。
先将数组从小到大排序,然后使用for循环,判断索引是否相等,不相等就是中间缺失的那个数,如果中间不缺数,最后返回索引即可,因为已经在循环体中自加1,最后返回的时候不用再加1。
此解法时间复杂度是O(nlog(n)),空间复杂度是O(1)。
public int missingNumber(int[] nums) {
if (nums == null || nums.length < 1) {
return 0;
}
Arrays.sort(nums);
int index;
for (index = 0; index < nums.length; index++) {
if (index != nums[index]) {
return index;
}
}
return index;
}
03 第二种解法
通过观察,我们可以发现,nums中的元素组成是一个以1为等差的等差数列,我们可以通过等差数列的和来找出缺失的元素,其求和公式为:
Sum = n*(A1+An)/2
题目中的数组是从0开始到n,即A1=0,An=n-1,我们计算的时候可以从1到数组长度,即A1=1,An=n,然后对其求和,借助for循环,此处有两种方式,一是用和去减每一个元素,最后剩下的就是缺失的元素;二是算出数组所有元素的和,再算等差数列的和与其的差值,就是缺失的元素。
此解法的时间复杂度是O(n),空间复杂度是O(1)。
public int missingNumber2(int[] nums) {
if (nums == null || nums.length < 1) {
return 0;
}
int sum = (nums.length*(1+nums.length))/2;
for (int n : nums) {
sum -= n;
}
return sum;
}
04 第三种解法
借助位运算中的异或(^)运算,通过一个运算公式:a^b^b = a
,我们可以算出缺失的那个数字。例如:
数组nums={0,1,2,4},数组的索引是{0,1,2,3}
missing=4^(0^0)^(1^1)^(2^2)^(4^3)
=3^(0^0)^(1^1)^(2^2)^(4^4)
=3
其中最开始的4就是数组的长度。
此解法的时间复杂度是O(n),空间复杂度是O(1)。
public int missingNumber3(int[] nums) {
if (nums == null || nums.length < 1) {
return 0;
}
int xor = nums.length;
for (int i = 0; i < nums.length; i ++) {
xor = xor ^ nums[i] ^ i;
}
return xor;
}
05 第四种解法
使用HashSet,先将数组中的每一个元素存入其中,然后利用for循环,从0到n,判断set中是否包含当前索引,不包含的就是缺失的那个数。
此解法也可以用HashMap做,思路都是一样的,时间复杂度是O(n),空间复杂度是O(n)。
public int missingNumber4(int[] nums) {
if (nums == null || nums.length < 1) {
return 0;
}
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
for (int i=0; i<=nums.length; i++) {
if (!set.contains(i)) {
return i;
}
}
return -1;
}
06 小结
算法专题目前已连续日更超过一个月,算法题文章65+篇,