C#LeetCode刷题之#219-存在重复元素 II​​​​​​​(Contains Duplicate II)

C#LeetCode刷题之#219-存在重复元素 II​​​​​​​(Contains Duplicate II)

问题

给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值最大为 k

输入: nums = [1,2,3,1], k = 3

输出: true

输入: nums = [1,0,1,1], k = 1

输出: true

输入: nums = [1,2,3,1,2,3], k = 2

输出: false 

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Input: nums = [1,2,3,1], k = 3

Output:true

Input: nums = [1,0,1,1], k = 1

Output: true

Input: nums = [1,2,3,1,2,3], k = 2

Output:false 

示例

public class Program {

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

        nums = new int[] { 1, 2, 3, 1, 2, 3 };
        var res = ContainsNearbyDuplicate(nums, 2);
        Console.WriteLine(res);

        nums = new int[] { 1, 0, 1, 1 };
        res = ContainsNearbyDuplicate(nums, 1);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static bool ContainsNearbyDuplicate(int[] nums, int k) {
        //暴力解法,此解法超时,LeetCode没有AC
        for(int i = 0; i < nums.Length; i++) {
            for(int j = 1; j <= k; j++) {
                if(i + j < nums.Length && nums[i] == nums[i + j]) {
                    return true;
                }
            }
        }
        return false;
    }

    private static bool ContainsNearbyDuplicate2(int[] nums, int k) {
        //哈希法
        var dic = new Dictionary<int, int>();
        //用字典存放键值对,key为数组中的值,value为数组的索引
        for(int i = 0; i < nums.Length; i++) {
            if(dic.ContainsKey(nums[i])) {
                //如果已经包含键
                int diss = i - dic[nums[i]];
                //记录索引差
                if(diss <= k) {
                    //达到题目要求,返回true
                    return true;
                } else {
                    //达不到题目要求时,记录值和索引
                    dic[nums[i]] = i;
                }
            } else {
                //如果不包含,记录值和索引
                dic[nums[i]] = i;
            }
        }
        return false;
    }

}

以上给出2种算法实现,以下是这个案例的输出结果:

False
True

分析:

显而易见,ContainsNearbyDuplicate的时间复杂度为: O(n^{2}) ,ContainsNearbyDuplicate2的时间复杂度为: O(n) 。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/3704

发表评论

登录后才能评论