217.存在重复元素

LeetCode LeetCode 数组哈希表排序

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

字数:1.1k 阅读 :

评论:

217.存在重复元素

217.存在重复元素

217.1 题目

给你一个整数数组 nums。如果任一值在数组中出现至少两次，返回 true；如果数组中每个元素互不相同，返回 false。

示例 1：

输入：nums = [1,2,3,1]
输出：true

示示例 2：

输入：nums = [1,2,3,4]
输出：false

示示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

提示：

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

217.2 题解

哈希表

// 方法一：哈希表
// 使用哈希表来记录每个数字的出现次数，如果有数字出现次数超过一次，则存在重复
static bool ContainsDuplicate1(int[] nums)
{
    // 创建一个 HashSet 用于存储出现过的数字
    HashSet<int> numSet = new HashSet<int>();

    // 遍历数组中的每个数字
    foreach (var num in nums)
    {
        // 尝试将当前数字添加到 HashSet 中，如果添加成功（即之前未出现过），Add 方法返回 true
        if (!numSet.Add(num))
        {
            // 如果添加失败，说明当前数字已经在 HashSet 中存在，表示存在重复，返回 true
            return true;
        }
    }

    // 如果遍历完整个数组都没有发现重复数字，返回 false
    return false;
}

排序

// 方法二：排序
// 先对数组进行排序，然后遍历数组，检查相邻元素是否相等
static bool ContainsDuplicate2(int[] nums)
{
    // 使用 Array.Sort 方法对数组进行升序排序
    Array.Sort(nums);

    // 遍历排序后的数组
    for (int i = 1; i < nums.Length; i++)
    {
        // 检查相邻元素是否相等，如果相等，表示存在重复，返回 true
        if (nums[i] == nums[i - 1])
        {
            return true;
        }
    }

    // 如果遍历完整个数组都没有发现重复数字，返回 false
    return false;
}

217.3 代码

using System;
using System.Collections.Generic;

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

        // 给你一个整数数组 nums 。如果任一值在数组中出现至少两次，返回 true；如果数组中每个元素互不相同，返回 false。

        // 示例 1：
        // 输入：nums = [1,2,3,1]
        // 输出：true

        // 示例 2：
        // 输入：nums = [1,2,3,4]
        // 输出：false

        // 示例 3：
        // 输入：nums = [1,1,1,3,3,4,3,2,4,2]
        // 输出：true

        // 提示：
        // 1 <= nums.length <= 105
        // -109 <= nums[i] <= 109

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { 1, 2, 3, 1 };
        bool result1 = ContainsDuplicate1(nums1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        bool result1_2 = ContainsDuplicate2(nums1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int[] nums2 = { 1, 2, 3, 4 };
        bool result2 = ContainsDuplicate1(nums2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        bool result2_2 = ContainsDuplicate2(nums2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        // 示例 3
        int[] nums3 = { 1, 1, 1, 3, 3, 4, 3, 2, 4, 2 };
        bool result3 = ContainsDuplicate1(nums3);
        Console.WriteLine($"示例3 方法1 输出：{result3}");
        bool result3_2 = ContainsDuplicate2(nums3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");

        #endregion
    }

    #region 答案

    // 方法一：哈希表
    // 使用哈希表来记录每个数字的出现次数，如果有数字出现次数超过一次，则存在重复
    static bool ContainsDuplicate1(int[] nums)
    {
        // 创建一个 HashSet 用于存储出现过的数字
        HashSet<int> numSet = new HashSet<int>();

        // 遍历数组中的每个数字
        foreach (var num in nums)
        {
            // 尝试将当前数字添加到 HashSet 中，如果添加成功（即之前未出现过），Add 方法返回 true
            if (!numSet.Add(num))
            {
                // 如果添加失败，说明当前数字已经在 HashSet 中存在，表示存在重复，返回 true
                return true;
            }
        }

        // 如果遍历完整个数组都没有发现重复数字，返回 false
        return false;
    }

    // 方法二：排序
    // 先对数组进行排序，然后遍历数组，检查相邻元素是否相等
    static bool ContainsDuplicate2(int[] nums)
    {
        // 使用 Array.Sort 方法对数组进行升序排序
        Array.Sort(nums);

        // 遍历排序后的数组
        for (int i = 1; i < nums.Length; i++)
        {
            // 检查相邻元素是否相等，如果相等，表示存在重复，返回 true
            if (nums[i] == nums[i - 1])
            {
                return true;
            }
        }

        // 如果遍历完整个数组都没有发现重复数字，返回 false
        return false;
    }


    #endregion
}

217.4 运行结果

示例1 方法1 输出：True
示例1 方法2 输出：True
示例2 方法1 输出：False
示例2 方法2 输出：False
示例3 方法1 输出：True
示例3 方法2 输出：True

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