数组中唯一元素中的第k个不同（或非重复）元素。-yiteyi-C++库

给定一个整数数组，打印 第k位 数组中的不同元素。给定的数组可能包含重复项，输出应打印 第k位 所有独特元素中的元素。如果 K 是多个不同的元素，打印 -1 . 例如：

null

Input : arr[] = {1, 2, 1, 3, 4, 2},         k = 2Output : 4First non-repeating element is 3Second non-repeating element is 4Input : arr[] = {1, 2, 50, 10, 20, 2},         k = 3Output : 10Input : {2, 2, 2, 2},         k = 2Output : -1

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

A. 简单解决方案 使用两个嵌套循环，外部循环从左到右拾取元素，内部循环检查拾取的元素是否存在于其他地方。如果不存在，则增加不同元素的计数。如果计数变为 K ，返回当前元素。

C++

                         // C++ program to print k-th distinct                       
                         // element in a given array                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns k-th distinct                       
                         // element in arr.                       
                         int                                     printKDistinct(                                     int                                     arr[],                                     int                                     n,                       
                                                 int                                     k)                       
                         {                       
                                                 int                                     dist_count = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 // Check if current element is                       
                                                 // present somewhere else.                       
                                                 int                                     j;                       
                                                 for                                     (j = 0; j < n; j++)                       
                                                 if                                     (i != j && arr[j] == arr[i])                       
                                                 break                                     ;                       
           
                                                 // If element is unique                       
                                                 if                                     (j == n)                       
                                                 dist_count++;                       
           
                                                 if                                     (dist_count == k)                       
                                                 return                                     arr[i];                       
                                                 }                       
           
                                                 return                                     -1;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main ()                       
                         {                       
                                                 int                                     ar[] = {1, 2, 1, 3, 4, 2};                       
                                                 int                                     n =                                     sizeof                                     (ar) /                                     sizeof                                     (ar[0]);                       
                                                 int                                     k = 2;                       
                                                 cout << printKDistinct(ar, n, k);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to print k-th distinct                       
                         // element in a given array                       
                         class                                     GFG                       
                         {                       
                                                 // Returns k-th distinct element in arr.                       
                                                 static                                     int                                     printKDistinct(                                     int                                     arr[],                       
                                                 int                                     n,                       
                                                 int                                     k)                       
                                                 {                       
                                                 int                                     dist_count =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                   
                                                 // Check if current element is                       
                                                 // present somewhere else.                       
                                                 int                                     j;                       
                                   
                                                 for                                     (j =                                     0                                     ; j < n; j++)                       
                                                 if                                     (i != j && arr[j] == arr[i])                       
                                                 break                                     ;                       
                                   
                                                 // If element is unique                       
                                                 if                                     (j == n)                       
                                                 dist_count++;                       
                                   
                                                 if                                     (dist_count == k)                       
                                                 return                                     arr[i];                       
                                                 }                       
                                   
                                                 return                                     -                                     1                                     ;                       
                                                 }                       
                                   
                                                 //Driver code                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                   
                                                 int                                     ar[] = {                                     1                                     ,                                     2                                     ,                                     1                                     ,                                     3                                     ,                                     4                                     ,                                     2                                     };                       
                                                 int                                     n = ar.length;                       
                                                 int                                     k =                                     2                                     ;                       
                                   
                                                 System.out.print(printKDistinct(ar, n, k));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

Python3

                         # Python3 program to print k-th distinct                       
                         # element in a given array                       
           
                         # Returns k-th distinct                       
                         # element in arr.                       
                         def                                     printKDistinct(arr, n, k):                       
                                                 dist_count                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                   
                                                 # Check if current element is                       
                                                 # present somewhere else.                       
                                                 j                                     =                                     0                       
                                                 while                                     j < n:                       
                                                 if                                     (i !                                     =                                     j                                     and                                     arr[j]                                     =                                     =                                     arr[i]):                       
                                                 break                       
                                                 j                                     +                                     =                                     1                       
           
                                                 # If element is unique                       
                                                 if                                     (j                                     =                                     =                                     n):                       
                                                 dist_count                                     +                                     =                                     1                       
           
                                                 if                                     (dist_count                                     =                                     =                                     k):                       
                                                 return                                     arr[i]                       
           
                                                 return                                     -                                     1                       
           
                         # Driver Code                       
                         ar                                     =                                     [                                     1                                     ,                                     2                                     ,                                     1                                     ,                                     3                                     ,                                     4                                     ,                                     2                                     ]                       
                         n                                     =                                     len                                     (ar)                       
                         k                                     =                                     2                       
                         print                                     (printKDistinct(ar, n, k))                       
           
                         # This code is contributed by Mohit Kumar                       

C#

                         // C# program to print k-th distinct                       
                         // element in a given array                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                                 // Returns k-th distinct element in arr                       
                                                 static                                     int                                     printKDistinct(                                     int                                     []arr,                       
                                                 int                                     n,                       
                                                 int                                     k)                       
                                                 {                       
                                   
                                                 int                                     dist_count = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                   
                                                 // Check if current element is                       
                                                 // present somewhere else.                       
                                                 int                                     j;                       
                                   
                                                 for                                     (j = 0; j < n; j++)                       
                                                 if                                     (i != j && arr[j] == arr[i])                       
                                                 break                                     ;                       
                                   
                                                 // If element is unique                       
                                                 if                                     (j == n)                       
                                                 dist_count++;                       
                                   
                                                 if                                     (dist_count == k)                       
                                                 return                                     arr[i];                       
                                                 }                       
                                   
                                                 return                                     -1;                       
                                                 }                       
                                   
                                                 //Driver code                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                   
                                                 int                                     []ar = {1, 2, 1, 3, 4, 2};                       
                                                 int                                     n = ar.Length;                       
                                                 int                                     k = 2;                       
                                   
                                                 Console.Write(printKDistinct(ar, n, k));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by nitn mittal                       

PHP

                         <?php                       
                         // PHP program to print k-th                       
                         // distinct element in a                       
                         // given array                       
           
           
                         // Returns k-th distinct                       
                         // element in arr.                       
                         function                                     printKDistinct(                                     $arr                                     ,                       
                                                 $n                                     ,                                     $k                                     )                       
                         {                       
                                                 $dist_count                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 // Check if current element                       
                                                 // is present somewhere else.                       
                                                 $j                                     ;                       
                                                 for                                     (                                     $j                                     = 0;                                     $j                                     <                                     $n                                     ;                                     $j                                     ++)                       
                                                 if                                     (                                     $i                                     !=                                     $j                                     &&                                     $arr                                     [                                     $j                                     ] ==                       
                                                 $arr                                     [                                     $i                                     ])                       
                                                 break                                     ;                       
           
                                                 // If element is unique                       
                                                 if                                     (                                     $j                                     ==                                     $n                                     )                       
                                                 $dist_count                                     ++;                       
           
                                                 if                                     (                                     $dist_count                                     ==                                     $k                                     )                       
                                                 return                                     $arr                                     [                                     $i                                     ];                       
                                                 }                       
           
                                                 return                                     -1;                       
                         }                       
           
                         // Driver Code                       
                         $ar                                     =                                     array                                     (1, 2, 1, 3, 4, 2);                       
                         $n                                     = sizeof(                                     $ar                                     ) / sizeof(                                     $ar                                     [0]);                       
                         $k                                     = 2;                       
                         echo                                     printKDistinct(                                     $ar                                     ,                                     $n                                     ,                                     $k                                     );                       
           
                         // This code is contributed by nitin mittal.                       
                         ?>                       

Javascript

                         <script>                       
                         //Javascript program to print k-th distinct                       
                         // element in a given array                       
           
                         // Returns k-th distinct                       
                         // element in arr.                       
                         function                                     printKDistinct(arr, n,  k)                       
                         {                       
                                                 var                                     dist_count = 0;                       
                                                 for                                     (                                     var                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 // Check if current element is                       
                                                 // present somewhere else.                       
                                                 var                                     j;                       
                                                 for                                     (j = 0; j < n; j++)                       
                                                 if                                     (i != j && arr[j] == arr[i])                       
                                                 break                                     ;                       
           
                                                 // If element is unique                       
                                                 if                                     (j == n)                       
                                                 dist_count++;                       
           
                                                 if                                     (dist_count == k)                       
                                                 return                                     arr[i];                       
                                                 }                       
           
                                                 return                                     -1;                       
                         }                       
           
                         var                                     ar = [1, 2, 1, 3, 4, 2];                       
                                                 var                                     n = ar.length;                       
                                                 var                                     k = 2;                       
                                                 document.write( printKDistinct(ar, n, k));                       
           
                         //This code is contributed by SoumikMondal                       
                         </script>                       

输出：

时间复杂性： O（n^2）

辅助空间： O（1）

一 有效解决方案 就是用散列来解决这个问题 O（n） 平均时间。 1) 创建一个空哈希表。 2) 从左向右遍历输入数组，并将元素及其计数存储在哈希表中。 3) 再次从左向右遍历输入数组。继续计数元素，计数为1。 4) 如果count变为k，则返回当前元素。

C++

                         // C++ program to print k-th                       
                         // distinct element in a                       
                         // given array                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns k-th distinct                       
                         // element in arr                       
                         int                                     printKDistinct(                                     int                                     arr[],                       
                                                 int                                     n,                                     int                                     k)                       
                         {                       
                                                 // Traverse input array and                       
                                                 // store counts if individual                       
                                                 // elements.                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > h;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 h[arr[i]]++;                       
           
                                                 // If size of hash is                       
                                                 // less than k.                       
                                                 if                                     (h.size() < k)                       
                                                 return                                     -1;                       
           
                                                 // Traverse array again and                       
                                                 // find k-th element with                       
                                                 // count as 1.                       
                                                 int                                     dist_count = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 if                                     (h[arr[i]] == 1)                       
                                                 dist_count++;                       
                                                 if                                     (dist_count == k)                       
                                                 return                                     arr[i];                       
                                                 }                       
           
                                                 return                                     -1;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main ()                       
                         {                       
                                                 int                                     ar[] = {1, 2, 1, 3, 4, 2};                       
                                                 int                                     n =                                     sizeof                                     (ar) /                                     sizeof                                     (ar[0]);                       
                                                 cout << printKDistinct(ar, n, 2);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to print k-th distinct                       
                         // element in a given array                       
                         import                                     java.util.*;                       
           
                         class                                     GfG                       
                         {                       
           
                         // Returns k-th distinct                       
                         // element in arr.                       
                         static                                     int                                     printKDistinct(                                     int                                     arr[],                       
                                                 int                                     n,                                     int                                     k)                       
                         {                       
                                                 //int dist_count = 0;                       
                                                 Map <Integer, Integer> h =                       
                                                 new                                     HashMap<Integer, Integer> ();                       
                                   
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 if                                     (h.containsKey(arr[i]))                       
                                                 h.put(arr[i], h.get(arr[i]) +                                     1                                     );                       
                                                 else                       
                                                 h.put(arr[i],                                     1                                     );                       
                                                 }                       
           
                                                 // If size of hash is                       
                                                 // less than k.                       
                                                 if                                     (h.size() < k)                       
                                                 return                                     -                                     1                                     ;                       
           
                                                 // Traverse array again and                       
                                                 // find k-th element with                       
                                                 // count as 1.                       
                                                 int                                     dist_count =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 if                                     (h.get(arr[i]) ==                                     1                                     )                       
                                                 dist_count++;                       
                                                 if                                     (dist_count == k)                       
                                                 return                                     arr[i];                       
                                                 }                       
                                                 return                                     -                                     1                                     ;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 int                                     ar[] = {                                     1                                     ,                                     2                                     ,                                     1                                     ,                                     3                                     ,                                     4                                     ,                                     2                                     };                       
                                                 int                                     n = ar.length;                       
                                                 System.out.println(printKDistinct(ar, n,                                     2                                     ));                       
                         }                       
                         }                       
           
                         // This code is contributed by                       
                         // Prerna Saini                       

Python3

                         # Python3 program to print k-th                       
                         # distinct element in a given array                       
                         def                                     printKDistinct(arr, size, KthIndex):                       
                                                 dict                                     =                                     {}                       
                                                 vect                                     =                                     []                       
                                                 for                                     i                                     in                                     range                                     (size):                       
                                                 if                                     (arr[i]                                     in                                     dict                                     ):                       
                                                 dict                                     [arr[i]]                                     =                                     dict                                     [arr[i]]                                     +                                     1                       
                                                 else                                     :                       
                                                 dict                                     [arr[i]]                                     =                                     1                       
                                                 for                                     i                                     in                                     range                                     (size):                       
                                                 if                                     (                                     dict                                     [arr[i]] >                                     1                                     ):                       
                                                 continue                       
                                                 else                                     :                       
                                                 KthIndex                                     =                                     KthIndex                                     -                                     1                       
                                                 if                                     (KthIndex                                     =                                     =                                     0                                     ):                       
                                                 return                                     arr[i]                       
                                                 return                                     -                                     1                       
           
                         # Driver Code                       
                         arr                                     =                                     [                                     1                                     ,                                     2                                     ,                                     1                                     ,                                     3                                     ,                                     4                                     ,                                     2                                     ]                       
                         size                                     =                                     len                                     (arr)                       
                         print                                     (printKDistinct(arr, size,                                     2                                     ))                       
           
                         # This code is contributed                       
                         # by Akhand Pratap Singh                       

C#

                         // C# program to print k-th distinct                       
                         // element in a given array                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GfG                       
                         {                       
           
                         // Returns k-th distinct                       
                         // element in arr.                       
                         static                                     int                                     printKDistinct(                                     int                                     []arr,                       
                                                 int                                     n,                                     int                                     k)                       
                         {                       
                                                 Dictionary<                                     int                                     ,                                     int                                     > h =                                     new                                     Dictionary<                                     int                                     ,                                     int                                     >();                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 if                                     (h.ContainsKey(arr[i]))                       
                                                 {                       
                                                 var                                     val = h[arr[i]];                       
                                                 h.Remove(arr[i]);                       
                                                 h.Add(arr[i], val + 1);                       
                                   
                                                 }                       
                                                 else                       
                                                 h.Add(arr[i], 1);                       
                                                 }                       
                                   
                                                 // If size of hash is                       
                                                 // less than k.                       
                                                 if                                     (h.Count < k)                       
                                                 return                                     -1;                       
           
                                                 // Traverse array again and                       
                                                 // find k-th element with                       
                                                 // count as 1.                       
                                                 int                                     dist_count = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 if                                     (h[arr[i]] == 1)                       
                                                 dist_count++;                       
                                                 if                                     (dist_count == k)                       
                                                 return                                     arr[i];                       
                                                 }                       
                                                 return                                     -1;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main (String[] args)                       
                         {                       
                                                 int                                     []ar = {1, 2, 1, 3, 4, 2};                       
                                                 int                                     n = ar.Length;                       
                                                 Console.WriteLine(printKDistinct(ar, n, 2));                       
                         }                       
                         }                       
           
                         // This code contributed by Rajput-Ji                       

Javascript

                         <script>                       
                         // Javascript program to print k-th distinct                       
                         // element in a given array                       
                                   
                                                 // Returns k-th distinct                       
                                                 // element in arr.                       
                                                 function                                     printKDistinct(arr,n,k)                       
                                                 {                       
                                                 // int dist_count = 0;                       
                                                 let h =                                     new                                     Map();                       
                                   
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                                 if                                     (h.has(arr[i]))                       
                                                 h.set(arr[i], h.get(arr[i]) + 1);                       
                                                 else                       
                                                 h.set(arr[i], 1);                       
                                                 }                       
                                   
                                                 // If size of hash is                       
                                                 // less than k.                       
                                                 if                                     (h.length < k)                       
                                                 return                                     -1;                       
                                   
                                                 // Traverse array again and                       
                                                 // find k-th element with                       
                                                 // count as 1.                       
                                                 let dist_count = 0;                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                                 if                                     (h.get(arr[i]) == 1)                       
                                                 dist_count++;                       
                                                 if                                     (dist_count == k)                       
                                                 return                                     arr[i];                       
                                                 }                       
                                                 return                                     -1;                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 let ar=[1, 2, 1, 3, 4, 2];                       
                                                 let n = ar.length;                       
                                                 document.write(printKDistinct(ar, n, 2));                       
                                   
                         // This code is contributed by unknown2108                       
                         </script>                       

输出：

时间复杂性： O（n）

辅助空间： O（n）

本文由 阿夫扎尔·安萨里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章