C#LeetCode刷题之#217-存在重复元素（Contains Duplicate）

问题

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

输入: [1,2,3,1]

输出: true

输入: [1,2,3,4]

输出: false

输入: [1,1,1,3,3,4,3,2,4,2]

输出: true 

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Input: [1,2,3,1]

Output: true

Input: [1,2,3,4]

Output: false

Input: [1,1,1,3,3,4,3,2,4,2]

Output: true 

示例

public class Program {

    public static void Main(string[] args) {
        int[] nums = null;

        nums = new int[] { 1, 2, 3, 4, 5, 6, 7, 7 };
        var res = ContainsDuplicate(nums);
        Console.WriteLine(res);

        nums = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 };
        res = ContainsDuplicate2(nums);
        Console.WriteLine(res);

        nums = new int[] { 1, 2, 3, 3, 5, 6, 7, 8 };
        res = ContainsDuplicate3(nums);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static bool ContainsDuplicate(int[] nums) {
        //暴力解法
        for(int i = 0; i < nums.Length; i++) {
            for(int j = i + 1; j < nums.Length; j++) {
                if(nums[i] == nums[j]) return true;
            }
        }
        return false;
    }

    private static bool ContainsDuplicate2(int[] nums) {
        //先排序，再使用单循环比较相邻值
        Array.Sort(nums);
        for(int i = 0; i < nums.Length - 1; i++) {
            if(nums[i] == nums[i + 1]) return true;
        }
        return false;
    }

    private static bool ContainsDuplicate3(int[] nums) {
        //哈希法
        var dic = new Dictionary<int, int>();
        foreach(var num in nums) {
            if(dic.ContainsKey(num)) return true;
            dic[num] = 0;
        }
        return false;
    }

}

以上给出3种算法实现，以下是这个案例的输出结果：

True
False
True

分析：

显而易见，ContainsDuplicate的时间复杂度为：  ，ContainsDuplicate2的时间复杂度需要考虑Array.Sort()具体使用的排序算法，ContainsDuplicate3的时间复杂度为：  。