【LeetCode】268. 丢失的数字

2023-12-13 07:20:41

268. 丢失的数字

难度:简单

题目

给定一个包含 [0, n]n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1

输入:nums = [3,0,1]
输出:2
解释:n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内。2 是丢失的数字,因为它没有出现在 nums 中。

示例 2

输入:nums = [0,1]
输出:2
解释:n = 2,因为有 2 个数字,所以所有的数字都在范围 [0,2] 内。2 是丢失的数字,因为它没有出现在 nums 中。

示例 3

输入:nums = [9,6,4,2,3,5,7,0,1]
输出:8
解释:n = 9,因为有 9 个数字,所以所有的数字都在范围 [0,9] 内。8 是丢失的数字,因为它没有出现在 nums 中。

示例 4

输入:nums = [0]
输出:1
解释:n = 1,因为有 1 个数字,所以所有的数字都在范围 [0,1] 内。1 是丢失的数字,因为它没有出现在 nums 中。

提示

  • n == nums.length
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= n
  • nums 中的所有数字都 独一无二

进阶:你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

个人题解

方法一:异或运算

异或性质:

0 ^ n = n

n ^ n = 0

思路:

  1. 由题独一无二可知,利用异或运算的性质即可求出这里面没有的数
  2. 即定义一个变量初始为0,将 0~n 的所有数与该变量异或,然后再与数组中所有数异或,最后的结果便是丢失的数字
class Solution {
    public int missingNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            result ^= i;
            result ^= nums[i];
        }
        result ^= nums.length;
        return result;
    }
}

复杂度分析

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

官方题解

方法一:排序

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return n;
    }
}

复杂度分析

  • 时间复杂度:O(n logn)
  • 空间复杂度:O(1)

方法二:哈希集合

首先遍历数组 nums ,将数组中的每个元素加入哈希集合,然后依次检查从 0 到 n 的每个整数是否在哈希集合中,不在哈希集合中的数字即为丢失的数字。由于哈希集合的每次添加元素和查找元素的时间复杂度都是 O(1) ,因此总时间复杂度是 O(n)

class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            set.add(nums[i]);
        }
        int missing = -1;
        for (int i = 0; i <= n; i++) {
            if (!set.contains(i)) {
                missing = i;
                break;
            }
        }
        return missing;
    }
}

复杂度分析

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

方法三:位运算

class Solution {
    public int missingNumber(int[] nums) {
        int xor = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            xor ^= nums[i];
        }
        for (int i = 0; i <= n; i++) {
            xor ^= i;
        }
        return xor;
    }
}

复杂度分析

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

方法四:数学

将从 0 到 n 的全部整数之和记为 total,根据高斯求和公式 total = (n * (n+1)) / 2

将数组 nums 的元素之和记为 arrSum,则 arrSum 比 total 少了丢失的一个数字,因此丢失的数字即为 total 于 arrSum 之差。

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int total = n * (n + 1) / 2;
        int arrSum = 0;
        for (int i = 0; i < n; i++) {
            arrSum += nums[i];
        }
        return total - arrSum;
    }
}

复杂度分析

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

作者:力扣官方题解
链接:https://leetcode.cn/problems/missing-number/solutions/1085105/diu-shi-de-shu-zi-by-leetcode-solution-naow/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

文章来源:https://blog.csdn.net/xxx1276063856/article/details/134867034
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。