检查给定数组中是否包含相互距离在k以内的重复元素-yiteyi-C++库

给定可能包含重复项的未排序数组。也给出了一个小于数组大小的数字k。编写一个函数，如果数组在k距离内包含重复项，则返回true。 例如：

null

Input: k = 3, arr[] = {1, 2, 3, 4, 1, 2, 3, 4}Output: falseAll duplicates are more than k distance away.Input: k = 3, arr[] = {1, 2, 3, 1, 4, 5}Output: true1 is repeated at distance 3.Input: k = 3, arr[] = {1, 2, 3, 4, 5}Output: falseInput: k = 3, arr[] = {1, 2, 3, 4, 4}Output: true

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 简单解决方案 就是运行两个循环。外循环选择每个元素“arr[i]”作为起始元素，内循环比较距离“arr[i]”k范围内的所有元素。该解的时间复杂度为O（kn）。我们可以解决这个问题 在Θ（n）时间内使用哈希。 这个想法是通过向散列中添加元素来实现的。我们还移除了距离当前元素超过k的元素。下面是详细的算法。 1）创建一个空哈希表。 2）从左向右遍历所有元素。让当前元素为’arr[i]’ ….a）如果哈希表中存在当前元素“arr[i]”，则返回true。 ….b）否则，将arr[i]添加到哈希中，如果i大于或等于k，则从哈希中删除arr[i-k]

C++

                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         /* C++ program to Check if a given array contains duplicate                       
                                                 elements within k distance from each other */                       
                         bool                                     checkDuplicatesWithinK(                                     int                                     arr[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 // Creates an empty hashset                       
                                                 unordered_set<                                     int                                     > myset;                       
           
                                                 // Traverse the input array                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 // If already present n hash, then we found                       
                                                 // a duplicate within k distance                       
                                                 if                                     (myset.find(arr[i]) != myset.end())                       
                                                 return                                     true                                     ;                       
           
                                                 // Add this item to hashset                       
                                                 myset.insert(arr[i]);                       
           
                                                 // Remove the k+1 distant item                       
                                                 if                                     (i >= k)                       
                                                 myset.erase(arr[i-k]);                       
                                                 }                       
                                                 return                                     false                                     ;                       
                         }                       
           
                         // Driver method to test above method                       
                         int                                     main ()                       
                         {                       
                                                 int                                     arr[] = {10, 5, 3, 4, 3, 5, 6};                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 if                                     (checkDuplicatesWithinK(arr, n, 3))                       
                                                 cout <<                                     "Yes"                                     ;                       
                                                 else                       
                                                 cout <<                                     "No"                                     ;                       
                         }                       
           
                         //This article is contributed by Chhavi                       

JAVA

                         /* Java program to Check if a given array contains duplicate                       
                                                 elements within k distance from each other */                       
                         import                                     java.util.*;                       
           
                         class                                     Main                       
                         {                       
                                                 static                                     boolean                                     checkDuplicatesWithinK(                                     int                                     arr[],                                     int                                     k)                       
                                                 {                       
                                                 // Creates an empty hashset                       
                                                 HashSet<Integer> set =                                     new                                     HashSet<>();                       
           
                                                 // Traverse the input array                       
                                                 for                                     (                                     int                                     i=                                     0                                     ; i<arr.length; i++)                       
                                                 {                       
                                                 // If already present n hash, then we found                       
                                                 // a duplicate within k distance                       
                                                 if                                     (set.contains(arr[i]))                       
                                                 return                                     true                                     ;                       
           
                                                 // Add this item to hashset                       
                                                 set.add(arr[i]);                       
           
                                                 // Remove the k+1 distant item                       
                                                 if                                     (i >= k)                       
                                                 set.remove(arr[i-k]);                       
                                                 }                       
                                                 return                                     false                                     ;                       
                                                 }                       
           
                                                 // Driver method to test above method                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     10                                     ,                                     5                                     ,                                     3                                     ,                                     4                                     ,                                     3                                     ,                                     5                                     ,                                     6                                     };                       
                                                 if                                     (checkDuplicatesWithinK(arr,                                     3                                     ))                       
                                                 System.out.println(                                     "Yes"                                     );                       
                                                 else                       
                                                 System.out.println(                                     "No"                                     );                       
                                                 }                       
                         }                       

Python 3

                         # Python 3 program to Check if a given array                       
                         # contains duplicate elements within k distance                       
                         # from each other                       
                         def                                     checkDuplicatesWithinK(arr, n, k):                       
           
                                                 # Creates an empty list                       
                                                 myset                                     =                                     []                       
           
                                                 # Traverse the input array                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                   
                                                 # If already present n hash, then we                       
                                                 # found a duplicate within k distance                       
                                                 if                                     arr[i]                                     in                                     myset:                       
                                                 return                                     True                       
           
                                                 # Add this item to hashset                       
                                                 myset.append(arr[i])                       
           
                                                 # Remove the k+1 distant item                       
                                                 if                                     (i >                                     =                                     k):                       
                                                 myset.remove(arr[i                                     -                                     k])                       
                                                 return                                     False                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                   
                                                 arr                                     =                                     [                                     10                                     ,                                     5                                     ,                                     3                                     ,                                     4                                     ,                                     3                                     ,                                     5                                     ,                                     6                                     ]                       
                                                 n                                     =                                     len                                     (arr)                       
                                                 if                                     (checkDuplicatesWithinK(arr, n,                                     3                                     )):                       
                                                 print                                     (                                     "Yes"                                     )                       
                                                 else                                     :                       
                                                 print                                     (                                     "No"                                     )                       
           
                         # This code is contributed by ita_c                       

C#

                         /* C# program to Check if a given                       
                         array contains duplicate elements                       
                         within k distance from each other */                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG                       
                         {                       
                                                 static                                     bool                                     checkDuplicatesWithinK(                                     int                                     []arr,                                     int                                     k)                       
                                                 {                       
                                                 // Creates an empty hashset                       
                                                 HashSet<                                     int                                     >                                     set                                     =                                     new                                     HashSet<                                     int                                     >();                       
           
                                                 // Traverse the input array                       
                                                 for                                     (                                     int                                     i = 0; i < arr.Length; i++)                       
                                                 {                       
                                                 // If already present n hash, then we found                       
                                                 // a duplicate within k distance                       
                                                 if                                     (                                     set                                     .Contains(arr[i]))                       
                                                 return                                     true                                     ;                       
           
                                                 // Add this item to hashset                       
                                                 set                                     .Add(arr[i]);                       
           
                                                 // Remove the k+1 distant item                       
                                                 if                                     (i >= k)                       
                                                 set                                     .Remove(arr[i - k]);                       
                                                 }                       
                                                 return                                     false                                     ;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main (String[] args)                       
                                                 {                       
                                                 int                                     []arr = {10, 5, 3, 4, 3, 5, 6};                       
                                                 if                                     (checkDuplicatesWithinK(arr, 3))                       
                                                 Console.WriteLine(                                     "Yes"                                     );                       
                                                 else                       
                                                 Console.WriteLine(                                     "No"                                     );                       
                                                 }                       
                         }                       
           
                         // This code has been contributed                       
                         // by 29AjayKumar                       

Javascript

                         <script>                       
           
                         /* Javascript program to Check if a given array contains duplicate                       
                                                 elements within k distance from each other */                       
                                   
                                   
                                                 function                                     checkDuplicatesWithinK(arr, n, k)                       
                                                 {                       
                                                 // Creates an empty hashset                       
                                                 let myset = [];                       
                                   
                                                 // Traverse the input array                       
                                                 for                                     (let i=0;i<n;i++)                       
                                                 {                       
                                                 // If already present n hash, then we found                       
                                                 // a duplicate within k distance                       
                                                 if                                     (arr.includes(arr[i]))                       
                                                 {                       
                                                 return                                     true                                     ;                       
                                                 }                       
                                                 // Add this item to hashset                       
                                                 myset.add(arr[i]);                       
                                   
                                                 // Remove the k+1 distant item                       
                                                 if                                     (i >= k)                       
                                                 {                       
                                                 index = array.indexOf(arr[i - k]);                       
                                                 array.splice(index, 1);                       
                                                 }                       
                                                 }                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                                 // Driver method to test above method                       
                                                 let arr = [10, 5, 3, 4, 3, 5, 6];                       
                                                 let n= arr.length;                       
                                                 if                                     (checkDuplicatesWithinK(arr, n, 3))                       
                                                 {                       
                                                 document.write(                                     "Yes"                                     );                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 document.write(                                     "No"                                     );                       
                                                 }                       
                                   
                                   
                                                 // This code is contributed by rag2127                       
                                   
                         </script>                       

输出：

Yes

本文由 阿努伊 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章