268.丢失的数字

LeetCode LeetCode 数组哈希表排序数学位运算二分查找

发布时间 : 2000-01-10 02:06

字数:1.9k 阅读 :

评论:

268.丢失的数字

268.丢失的数字

268.1 题目

给定一个包含 [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 中的所有数字都独一无二

进阶：

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

268.2 题解

HashSet判断元素是否存在

// 方法一：HashSet判断元素是否存在
// 使用 HashSet 存储数组元素，然后从 [0, n] 中找到第一个不在 HashSet 中的数字
static int MissingNumber1(int[] nums)
{
    // 创建一个 HashSet 用于存储数组元素
    HashSet<int> numSet = new HashSet<int>(nums);

    // 获取数组的长度 n
    int n = nums.Length;

    // 遍历 [0, n] 区间的所有数字
    for (int i = 0; i <= n; i++)
    {
        // 判断当前数字是否在 HashSet 中，如果不在，则返回该数字
        if (!numSet.Contains(i))
        {
            return i;
        }
    }

    // 如果数组本身就是 [0, n]，则不会执行到这一步，返回 -1 表示未找到缺失的数字
    return -1;
}

等差数列求和

// 方法二：等差数列求和
// 利用等差数列求和公式，计算 [0, n] 的和，减去数组元素的和，得到缺失的数字
static int MissingNumber2(int[] nums)
{
    // 获取数组的长度 n
    int n = nums.Length;

    // 计算 [0, n] 的期望和
    int expectedSum = n * (n + 1) / 2;

    // 计算数组元素的实际和
    int actualSum = 0;

    // 遍历数组，累加数组元素的值
    foreach (int num in nums)
    {
        actualSum += num;
    }

    // 返回期望和减去实际和，即为缺失的数字
    return expectedSum - actualSum;
}

排序数组后判断值和索引是否相等

// 方法三：排序数组后判断值和索引是否相等
// 排序数组，遍历判断值和索引是否相等，找到第一个不匹配的值的索引即为缺失的数字
static int MissingNumber3(int[] nums)
{
    // 对数组进行升序排序
    Array.Sort(nums);

    // 获取数组的长度 n
    int n = nums.Length;

    // 遍历排序后的数组
    for (int i = 0; i < n; i++)
    {
        // 判断值和索引是否相等，如果不相等，则返回当前索引作为缺失的数字
        if (nums[i] != i)
        {
            return i;
        }
    }

    // 如果数组本身就是 [0, n-1]，则 n 为缺失的数字
    return n;
}

268.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个包含 [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 中。

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { 3, 0, 1 };
        int result1 = MissingNumber1(nums1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        int result1_2 = MissingNumber2(nums1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");
        int result1_3 = MissingNumber3(nums1);
        Console.WriteLine($"示例1 方法3 输出：{result1_3}");

        // 示例 2
        int[] nums2 = { 0, 1 };
        int result2 = MissingNumber1(nums2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        int result2_2 = MissingNumber2(nums2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");
        int result2_3 = MissingNumber3(nums2);
        Console.WriteLine($"示例2 方法3 输出：{result2_3}");

        // 示例 3
        int[] nums3 = { 9, 6, 4, 2, 3, 5, 7, 0, 1 };
        int result3 = MissingNumber1(nums3);
        Console.WriteLine($"示例3 方法1 输出：{result3}");
        int result3_2 = MissingNumber2(nums3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");
        int result3_3 = MissingNumber3(nums3);
        Console.WriteLine($"示例3 方法3 输出：{result3_3}");

        // 示例 4
        int[] nums4 = { 0 };
        int result4 = MissingNumber1(nums4);
        Console.WriteLine($"示例4 方法1 输出：{result4}");
        int result4_2 = MissingNumber2(nums4);
        Console.WriteLine($"示例4 方法2 输出：{result4_2}");
        int result4_3 = MissingNumber3(nums4);
        Console.WriteLine($"示例4 方法3 输出：{result4_3}");

        #endregion
    }

    #region 答案

    // 方法一：HashSet判断元素是否存在
    // 使用 HashSet 存储数组元素，然后从 [0, n] 中找到第一个不在 HashSet 中的数字
    static int MissingNumber1(int[] nums)
    {
        // 创建一个 HashSet 用于存储数组元素
        HashSet<int> numSet = new HashSet<int>(nums);

        // 获取数组的长度 n
        int n = nums.Length;

        // 遍历 [0, n] 区间的所有数字
        for (int i = 0; i <= n; i++)
        {
            // 判断当前数字是否在 HashSet 中，如果不在，则返回该数字
            if (!numSet.Contains(i))
            {
                return i;
            }
        }

        // 如果数组本身就是 [0, n]，则不会执行到这一步，返回 -1 表示未找到缺失的数字
        return -1;
    }

    // 方法二：等差数列求和
    // 利用等差数列求和公式，计算 [0, n] 的和，减去数组元素的和，得到缺失的数字
    static int MissingNumber2(int[] nums)
    {
        // 获取数组的长度 n
        int n = nums.Length;

        // 计算 [0, n] 的期望和
        int expectedSum = n * (n + 1) / 2;

        // 计算数组元素的实际和
        int actualSum = 0;

        // 遍历数组，累加数组元素的值
        foreach (int num in nums)
        {
            actualSum += num;
        }

        // 返回期望和减去实际和，即为缺失的数字
        return expectedSum - actualSum;
    }

    // 方法三：排序数组后判断值和索引是否相等
    // 排序数组，遍历判断值和索引是否相等，找到第一个不匹配的值的索引即为缺失的数字
    static int MissingNumber3(int[] nums)
    {
        // 对数组进行升序排序
        Array.Sort(nums);

        // 获取数组的长度 n
        int n = nums.Length;

        // 遍历排序后的数组
        for (int i = 0; i < n; i++)
        {
            // 判断值和索引是否相等，如果不相等，则返回当前索引作为缺失的数字
            if (nums[i] != i)
            {
                return i;
            }
        }

        // 如果数组本身就是 [0, n-1]，则 n 为缺失的数字
        return n;
    }

    #endregion
}

268.4 运行结果

示例1 方法1 输出：2
示例1 方法2 输出：2
示例1 方法3 输出：2
示例2 方法1 输出：2
示例2 方法2 输出：2
示例2 方法3 输出：2
示例3 方法1 输出：8
示例3 方法2 输出：8
示例3 方法3 输出：8
示例4 方法1 输出：1
示例4 方法2 输出：1
示例4 方法3 输出：1

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com