删除m个项目后的最小独立元素数-yiteyi-C++库

给定一个项目数组，第i个索引元素表示项目id，给定一个数字m，任务是删除m个元素，这样就应该剩下最小的不同id。打印不同id的编号。例如：

null

Input : arr[] = { 2, 2, 1, 3, 3, 3}             m = 3Output : 1Remove 1 and both 2's.So, only 3 will be left that's why distinct id is 1.Input : arr[] = { 2, 4, 1, 5, 3, 5, 1, 3}             m = 2Output : 3Remove 2 and 4 completely. So, remaining ids are 1, 3 and 5 i.e. 3

问：摩根士丹利

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

1-计算元素的出现次数并将其存储在哈希中。 2-对散列进行排序。 3-开始从哈希中删除频率计数小于m的元素。 4-返回散列中剩余的值数。

C++

                         // C++ program for above implementation                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to find distintc id's                       
                         int                                     distinctIds(                                     int                                     arr[],                                     int                                     n,                                     int                                     mi)                       
                         {                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > m;                       
                                                 vector<pair<                                     int                                     ,                                     int                                     > > v;                       
                                                 int                                     count = 0;                       
           
                                                 // Store the occurrence of ids                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 m[arr[i]]++;                       
           
                                                 // Store into the vector second as first and vice-versa                       
                                                 for                                     (                                     auto                                     it = m.begin(); it != m.end(); it++)                       
                                                 v.push_back(make_pair(it->second, it->first));                       
           
                                                 // Sort the vector                       
                                                 sort(v.begin(), v.end());                       
           
                                                 int                                     size = v.size();                       
           
                                                 // Start removing elements from the beginning                       
                                                 for                                     (                                     int                                     i = 0; i < size; i++) {                       
           
                                                 // Remove if current value is less than                       
                                                 // or equal to mi                       
                                                 if                                     (v[i].first <= mi) {                       
                                                 mi -= v[i].first;                       
                                                 count++;                       
                                                 }                       
           
                                                 // Return the remaining size                       
                                                 else                       
                                                 return                                     size - count;                       
                                                 }                       
                                                 return                                     size - count;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 2, 3, 1, 2, 3, 3 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
           
                                                 int                                     m = 3;                       
           
                                                 cout << distinctIds(arr, n, m);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         import                                     java.util.*;                       
           
                         class                                     Solution {                       
                                                 static                                     int                                     distinctIds(                                     int                                     arr[],                                     int                                     n,                                     int                                     m)                       
                                                 {                       
                                                 // Creating HashMap to store frequency count                       
                                                 HashMap<Integer, Integer> h =                                     new                                     HashMap<>();                       
           
                                                 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                                     );                       
                                                 }                       
                                                 }                       
           
                                                 // Creating a list to sort HashMap according to                       
                                                 // values                       
                                                 List<Map.Entry<Integer, Integer> > l                       
                                                 =                                     new                                     LinkedList<Map.Entry<Integer, Integer> >(                       
                                                 h.entrySet());                       
           
                                                 // sorting using Comparator                       
                                                 Collections.sort(                       
                                                 l,                       
                                                 new                                     Comparator<Map.Entry<Integer, Integer> >() {                       
                                                 public                                     int                                     compare(                       
                                                 Map.Entry<Integer, Integer> o1,                       
                                                 Map.Entry<Integer, Integer> o2)                       
                                                 {                       
                                                 return                                     o1.getValue() - o2.getValue();                       
                                                 }                       
                                                 });                       
           
                                                 // Creating new map after sorting and also                       
                                                 // maintaining insertion order                       
                                                 LinkedHashMap<Integer, Integer> lh                       
                                                 =                                     new                                     LinkedHashMap<>();                       
                                                 for                                     (Map.Entry<Integer, Integer> e : l) {                       
                                                 lh.put(e.getKey(), e.getValue());                       
                                                 }                       
           
                                                 for                                     (Integer i : lh.keySet()) {                       
                                                 // removing element from whose frquency count is                       
                                                 // less than m ,Sorted manner to get minimum                       
                                                 // distinct ids                       
                                                 if                                     (h.get(i) <= m) {                       
                                                 m -= h.get(i);                       
                                                 h.remove(i);                       
                                                 }                       
                                                 }                       
           
                                                 return                                     h.size();                       
                                                 }                       
           
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 // TODO Auto-generated method stub                       
                                                 int                                     arr[] = {                                     2                                     ,                                     4                                     ,                                     1                                     ,                                     5                                     ,                                     3                                     ,                                     5                                     ,                                     1                                     ,                                     3                                     };                       
                                                 int                                     m =                                     2                                     ;                       
           
                                                 System.out.println(distinctIds(arr, arr.length, m));                       
                                                 }                       
                         }                       

Python3

                         # Python program for above implementation                       
           
                         # Function to find distintc id's                       
                         def                                     distinctIds(arr, n, mi):                       
                                                 m                                     =                                     {}                       
                                                 v                                     =                                     []                       
                                                 count                                     =                                     0                       
           
                                                 # Store the occurrence of ids                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 if                                     arr[i]                                     in                                     m:                       
                                                 m[arr[i]]                                     +                                     =                                     1                       
                                                 else                                     :                       
                                                 m[arr[i]]                                     =                                     1                       
           
                                                 # Store into the list value as key and vice-versa                       
                                                 for                                     i                                     in                                     m:                       
                                                 v.append([m[i],i])                       
           
                                                 v.sort()                       
                                                 size                                     =                                     len                                     (v)                       
           
                                                 # Start removing elements from the beginning                       
                                                 for                                     i                                     in                                     range                                     (size):                       
                                   
                                                 # Remove if current value is less than                       
                                                 # or equal to mi                       
                                                 if                                     (v[i][                                     0                                     ] <                                     =                                     mi):                       
                                                 mi                                     -                                     =                                     v[i][                                     0                                     ]                       
                                                 count                                     +                                     =                                     1                       
                                   
                                                 else                                     :                                     # Return the remaining size                       
                                                 return                                     size                                     -                                     count                       
                                                 return                                     size                                     -                                     count                       
           
                         # Driver code                       
                         arr                                     =                                     [                                     2                                     ,                                     3                                     ,                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     3                                     ]                       
                         n                                     =                                     len                                     (arr)                       
           
                         m                                     =                                     3                       
           
                         # To display the result                       
                         print                                     (distinctIds(arr, n, m))                       
           
                         # This code is contributed by rohitsingh07052                       

C#

                         // C# program for Minimum number of                       
                         // distinct elements after removing m items                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
                         class                                     GFG                       
                         {                       
           
                                                 // Function to find distintc id's                       
                                                 static                                     int                                     distinctIds(                                     int                                     [] arr,                                     int                                     n,                                     int                                     mi)                       
                                                 {                       
           
                                                 Dictionary<                                     int                                     ,                                     int                                     > m =                                     new                                     Dictionary<                                     int                                     ,                                     int                                     >();                       
                                                 int                                     count = 0;                       
                                                 int                                     size = 0;                       
           
                                                 // Store the occurrence of ids                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
           
                                                 // If the key is not add it to map                       
                                                 if                                     (m.ContainsKey(arr[i]) ==                                     false                                     )                       
                                                 {                       
                                                 m[arr[i]] = 1;                       
                                                 size++;                       
                                                 }                       
           
                                                 // If it is present then increase the value by 1                       
                                                 else                       
                                                 {                       
                                                 m[arr[i]]++;                       
                                                 }                       
                                                 }                       
           
                                                 // Start removing elements from the beginning                       
                                                 foreach                                     (KeyValuePair<                                     int                                     ,                                     int                                     > mp                                     in                                     m)                       
                                                 {                       
           
                                                 // Remove if current value is less than                       
                                                 // or equal to mi                       
                                                 if                                     (mp.Key <= mi)                       
                                                 {                       
                                                 mi -= mp.Key;                       
                                                 count++;                       
                                                 }                       
                                                 }                       
                                                 return                                     size - count;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 static                                     void                                     Main()                       
                                                 {                       
           
                                                 // TODO Auto-generated method stub                       
                                                 int                                     [] arr = {2, 3, 1, 2, 3, 3};                       
                                                 int                                     m = 3;                       
           
                                                 Console.WriteLine(distinctIds(arr, arr.Length, m));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by divyeshrabadiya07                       

Javascript

                         <script>                       
           
                         // Javascript program for above implementation                       
           
                         // Function to find distintc id's                       
                         function                                     distinctIds(arr, n, mi)                       
                         {                       
                                                 var                                     m =                                     new                                     Map();                       
                                                 var                                     v = [];                       
                                                 var                                     count = 0;                       
           
                                                 // Store the occurrence of ids                       
                                                 for                                     (                                     var                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 if                                     (m.has(arr[i]))                       
                                                 m.set(arr[i], m.get(arr[i])+1)                       
                                                 else                       
                                                 m.set(arr[i], 1)                       
                                                 }                       
           
                                                 // Store into the vector second as first and vice-versa                       
                                                 m.forEach((value, key) => {                       
                                   
                                                 v.push([value, key]);                       
                                                 });                       
           
                                                 // Sort the vector                       
                                                 v.sort()                       
           
                                                 var                                     size = v.length;                       
           
                                                 // Start removing elements from the beginning                       
                                                 for                                     (                                     var                                     i = 0; i < size; i++) {                       
           
                                                 // Remove if current value is less than                       
                                                 // or equal to mi                       
                                                 if                                     (v[i][0] <= mi) {                       
                                                 mi -= v[i][0];                       
                                                 count++;                       
                                                 }                       
           
                                                 // Return the remaining size                       
                                                 else                       
                                                 return                                     size - count;                       
                                                 }                       
                                                 return                                     size - count;                       
                         }                       
           
                         // Driver code                       
                         var                                     arr = [2, 3, 1, 2, 3, 3 ];                       
                         var                                     n = arr.length;                       
                         var                                     m = 3;                       
                         document.write( distinctIds(arr, n, m));                       
           
                         // This code is contributed by immportantly.                       
                         </script>                       

输出：

时间复杂性： O（n日志n）本文由 萨希尔·查布拉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章