LeetCode Top Interview Questions 268. Missing Number (Java版; Easy)
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
LeetCode Top Interview Questions 268. Missing Number (Java版; Easy)
题目描述
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
Example 1:
Input: [3,0,1]
Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
第一次做; 使用数学公式: 等差数列求和公式, (1+n)*n一定能被2整除, 因为(1+n)*n是偶数; 时间复杂度O(1),空间复杂度O(1)
class Solution {
public int missingNumber(int[] nums) {
int sum = 0, n=nums.length;
for(int i=0; i<nums.length;i++)
sum += nums[i];
return (1+n)*n/2-sum;
}
}第一次做; 位运算, 异或; 非常巧妙! 核心: 先计算得到123…n的结果res1, 再计算得到nums[0]nums[1]nums[2]…nums[n-1]的结果res2, 根据题意可知, 缺失的数字出现了一次, 其余的数字都出现两次, 根据异或的性质, a^a=0, 所以res1^res2就是最终的结果; 时间复杂度O(N), 空间复杂度O(1)
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int res = 0;
for(int i=0; i<n; i++){
res = res ^ nums[i];
res = res ^ i;
}
res = res ^ n;
return res;
}
}简洁一点地写法
class Solution {
public int missingNumber(int[] nums) {
int res = 0;
for(int i=0; i<nums.length; i++){
res ^= nums[i];
res ^= i;
}
return res^nums.length;
}
}第一次做; 鸽巢原理(抽屉原理), 配合一个临时变量记录n是否出现过; 核心:如果n没出现过,那么数组中每个元素的值都等于该元素对应的索引, n是缺失值; 如果n出现过,那么数组中某个索引不等于该位置元素的值, 该索引就是缺失值; 逻辑很清晰, 就是执行速度比较慢, 时间复杂度O(N), 空间复杂度O(1), 肯定存在非常巧妙的方法
/*
整体是鸽巢原理(抽屉原理)
按照有无n这个元素分成两种情况判断
*/
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
//检查是否出现过n
int tmp = n-1;
int i = 0;
//各回各家
while(i<n){
int cur = nums[i];
if(cur==n){
tmp = n;
i++;
}
else{
if(cur==i)
i++;
else
swap(nums, i, cur);
}
}
/*
核心:
如果没出现过n, 那么每个鸽子都回到了正确的巢穴, n是缺少的元素
如果出现过n,那么和元素(鸽子)不对应的索引(巢穴)就是缺少的元素
*/
int missing = n;
for(int j=0; j<n; j++){
if(nums[j]!=j && tmp==n){
missing = j;
break;
}
}
return missing;
}
public void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
第一次做; 排序的方法, 先排序, 再遍历数组检查索引是否等于对应的元素的值; 时间复杂度O(NlogN), 空间复杂度O(N)
class Solution {
public int missingNumber(int[] nums) {
Arrays.sort(nums);
for(int i=0; i<nums.length; i++){
if(nums[i]!=i)
return i;
}
//执行到这里, 说明每个鸽子都回到了正确的巢, 那么缺失值就是n
return nums.length;
}
}
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
“LeetCode Top Interview Questions 268. Missing Number (Java版; Easy)” 的相关文章
