删除k个元素后的最大独立元素数-yiteyi-C++库

给定一个数组 arr[] 包含 N 元素。问题是要找到删除后不同元素（非重复）的最大数量 K 数组中的元素。注： 1<=k<=n。 例如：

null

Input : arr[] = {5, 7, 5, 5, 1, 2, 2}, k = 3Output : 4Remove 2 occurrences of element 5 and1 occurrence of element 2.Input : arr[] = {1, 2, 3, 4, 5, 6, 7}, k = 5Output : 2Input : arr[] = {1, 2, 2, 2}, k = 1Output : 1

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

方法： 以下是步骤：

1.从给定数组生成一个多集合。

2.在进行此多集时，检查当前元素是否存在于多集中，如果它已经存在，则只需减小k值，不要插入多集。

3.如果k变为0，则只需将值放入multiset。

4.遍历整个给定数组后，

a）如果k不等于零，则意味着多重集仅由唯一元素组成，我们必须从多重集中删除任何k元素，使k=0，因此在这种情况下，答案将是多重集的大小减去当时的k值。

b）如果k等于零，则意味着多重集合中可能存在重复值，因此将所有值放在一个集合中，该集合的大小将是移除k个元素后不同元素的数量

C++

                         // CPP implementation of the above approach                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                                   
                         // function to find maximum distinct elements                       
                         // after removing k elements                       
                         int                                     maxDistinctNum(                                     int                                     a[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 int                                     i;                       
                                                 multiset<                                     int                                     > s;                       
                                                 // making multiset from given array                       
                                                 for                                     (i=0;i<n;i++){                       
                                                 if                                     (s.find(a[i])==s.end()||k==0)                       
                                                 s.insert(a[i]);                       
                                                 else                       
                                                 {                       
                                                 k--;                       
                                                 }                       
                                                 }                       
                                   
                                                 if                                     (k!=0)                       
                                                 return                                     s.size()-k;                       
                                                 else                                     {                       
                                                 set<                                     int                                     > st;                       
                                                 for                                     (                                     auto                                     it:s){                       
                                                 st.insert(it);                       
                                                 }                       
                                                 return                                     st.size();                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 5, 7, 5, 5, 1, 2, 2 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 int                                     k = 3;                       
                                   
                                                 // Function Call                       
                                                 cout <<                                     "Maximum distinct elements = "                       
                                                 << maxDistinctNum(arr, n, k);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java implementation of the                       
                         // above approach                       
                         import                                     java.util.*;                       
                         class                                     GFG{                       
                                   
                         // Function to find maximum                       
                         // distinct elements after                       
                         // removing k elements                       
                         static                                     int                                     maxDistinctNum(                                     int                                     arr[],                       
                                                 int                                     n,                                     int                                     k)                       
                         {                       
                                                 HashMap<Integer,                       
                                                 Integer> numToFreq =                                     new                                     HashMap<>();                       
           
                                                 // Build frequency map                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n ; i++)                       
                                                 {                       
                                                 numToFreq.put(arr[i],                       
                                                 numToFreq.getOrDefault(arr[i],                                     0                                     ) +                                     1                                     );                       
                                                 }                       
           
                                                 int                                     result =                                     0                                     ;                       
           
                                                 // Min-heap                       
                                                 PriorityQueue<Integer> minHeap =                       
                                                 new                                     PriorityQueue<Integer>();                       
           
                                                 // Add all number with freq=1 to                       
                                                 // result and push others to minHeap                       
                                                 for                                     (Map.Entry<Integer,                       
                                                 Integer> p : numToFreq.entrySet())                       
                                                 {                       
                                                 if                                     (p.getValue() ==                                     1                                     )                       
                                                 ++result;                       
                                                 else                       
                                                 minHeap.add(p.getValue());                       
                                                 }                       
           
                                                 // Perform k operations                       
                                                 while                                     (k !=                                     0                                     && !minHeap.isEmpty())                       
                                                 {                       
                                                 // Pop the top() element                       
                                                 Integer t = minHeap.poll();                       
                                   
                                                 // Increment Result                       
                                                 if                                     (t ==                                     1                                     )                       
                                                 {                       
                                                 ++result;                       
                                                 }                       
           
                                                 // Reduce t and k                       
                                                 // Push it again                       
                                                 else                       
                                                 {                       
                                                 --t;                       
                                                 --k;                       
                                                 minHeap.add(t);                       
                                                 }                       
                                                 }                       
           
                                                 // Return result                       
                                                 return                                     result;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     arr[] = {                                     5                                     ,                                     7                                     ,                                     5                                     ,                                     5                                     ,                                     1                                     ,                                     2                                     ,                                     2                                     };                       
                                                 int                                     n = arr.length;                       
                                                 int                                     k =                                     3                                     ;                       
           
                                                 // Function Call                       
                                                 System.out.println(                                     "Maximum distinct elements = "                                     +                       
                                                 maxDistinctNum(arr, n, k));                       
                         }                       
                         }                       
           
                         // This code is contributed by rutvik_56                       

Javascript

                         <script>                       
           
                         // Javascript implementation of the above approach                       
                                   
                         // function to find maximum distinct elements                       
                         // after removing k elements                       
                         function                                     maxDistinctNum(a, n, k)                       
                         {                       
                                                 var                                     i;                       
                                                 var                                     s = [];                       
                                                 // making multiset from given array                       
                                                 for                                     (i=0;i<n;i++){                       
                                                 if                                     (!s.includes(a[i])||k==0)                       
                                                 s.push(a[i]);                       
                                                 else                       
                                                 {                       
                                                 k--;                       
                                                 }                       
                                                 }                       
                                   
                                                 if                                     (k!=0)                       
                                                 return                                     s.size-k;                       
                                                 else                                     {                       
                                                 var                                     st =                                     new                                     Set();                       
                                                 s.forEach(element => {                       
                                                 st.add(element);                       
                                                 });                       
                                   
                                                 return                                     st.size;                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         var                                     arr = [5, 7, 5, 5, 1, 2, 2];                       
                         var                                     n = arr.length;                       
                         var                                     k = 3;                       
           
                         // Function Call                       
                         document.write(                                     "Maximum distinct elements = "                       
                                                 +  maxDistinctNum(arr, n, k));                       
           
                         // This code is contributed by itsok.                       
                         </script>                       

输出

Maximum distinct elements = 4

输出：

Maximum distinct elements = 4

时间复杂性： O（k*logd），在哪里 D 是给定数组中不同元素的数目。

另一种方法： 请按照以下步骤解决此问题：

找出不同玩具的数量。
除一个元素外的元素数之和构成每个不同的玩具。
如果大于或等于K，则检查总和，然后返回所有不同的元素。
否则，减少不同元素的数量并填充K。
返回向量的大小。

以下是上述方法的实施情况：

C++

                         // C++ code for the above approach                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                         // function to return maximum number of distinct Toys                       
                         int                                     MaxNumber(                                     int                                     arr[],                                     int                                     N,                                     int                                     K)                       
                         {                       
                                                 // Count Number of distinct Number                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > mp;                       
                                                 for                                     (                                     int                                     i = 0; i < N; i++) {                       
                                                 mp[arr[i]]++;                       
                                                 }                       
                                                 // push them into vector                       
                                                 vector<                                     int                                     > v1;                       
                                                 for                                     (                                     auto                                     i : mp) {                       
                                                 v1.push_back(i.second);                       
                                                 }                       
                                                 // add number of element except one element from every                       
                                                 // distinct element                       
                                                 int                                     temp = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < v1.size(); i++) {                       
                                                 temp += v1[i] - 1;                       
                                                 }                       
                                                 // check if it is greater then simply return size of                       
                                                 // vector otherwise decrement size of vector to fill k                       
                                                 if                                     (K <= temp) {                       
                                                 return                                     v1.size();                       
                                                 }                       
                                                 else                                     {                       
                                                 K = K - temp;                       
                                                 int                                     ans = v1.size();                       
                                                 while                                     (K) {                       
                                                 ans--;                       
                                                 K--;                       
                                                 }                       
                                                 return                                     ans;                       
                                                 }                       
                         }                       
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 // array                       
                                                 int                                     arr[] = { 10, 10, 10, 50, 50 };                       
                                                 int                                     K = 3;                       
                                                 // size of array                       
                                                 int                                     N =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 cout << MaxNumber(arr, N, K) << endl;                       
                                                 return                                     0;                       
                         }                       

输出

时间复杂性： O（N）

空间复杂性： O（N）

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

THE END

技术文章