
问题
给定一个整数数组和一个整数 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的时间复杂度为: ,ContainsNearbyDuplicate2的时间复杂度为:
。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3704。