找出包含k个不同元素的数组所需的最小变化

本文概述

• C ++
• Java
• Python3
• C#

给定一个大小为N的数组和一个数字K的数组，任务是找到最小的元素被替换为任何数字，使数组包含K个不同的元素。

注意：

该数组可能包含重复元素。

例子：

输入：arr [] = {1, 2, 2, 8}, k = 1
输出：2
要更改的元素为1, 8
输入：arr [] = {1, 2, 7, 8, 2, 3, 2, 3}, k = 2
输出：3
要更改的元素是1, 7, 8

方法:因为任务是替换数组中的最小元素，所以我们不会替换数组中频率更高的元素。因此，只需定义一个数组freq[]，它存储数组arr中出现的每个数字的频率，然后将freq按降序排序。所以，不需要替换频率数组的前k个元素。

下面是上述方法的实现：

C ++

//CPP program to minimum changes required 
//in an array for k distinct elements.
#include <bits/stdc++.h>
using namespace std;
  
#define MAX 100005
  
//Function to minimum changes required 
//in an array for k distinct elements.
int Min_Replace( int arr[], int n, int k)
{
     sort(arr, arr + n);
  
     //Store the frequency of each element
     int freq[MAX];
      
     memset (freq, 0, sizeof freq);
      
     int p = 0;
     freq
 = 1;
      
     //Store the frequency of elements
     for ( int i = 1; i <n; i++) {
         if (arr[i] == arr[i - 1])
             ++freq
;
         else
             ++freq[++p];
     }
  
     //Sort frequencies in descending order
     sort(freq, freq + n, greater<int>());
      
     //To store the required answer
     int ans = 0;
     for ( int i = k; i <= p; i++)
         ans += freq[i];
          
     //Return the required answer
     return ans;
}
  
//Driver code
int main()
{
     int arr[] = { 1, 2, 7, 8, 2, 3, 2, 3 };
      
     int n = sizeof (arr) /sizeof (arr[0]);
      
     int k = 2;
      
     cout <<Min_Replace(arr, n, k);
      
     return 0;
}

Java

//C# program to minimum changes required 
//in an array for k distinct elements.
import java.util.*;
  
class GFG
{
     static int MAX = 100005 ;
      
     //Function to minimum changes required 
     //in an array for k distinct elements.
     static int Min_Replace( int [] arr, int n, int k)
     {
         Arrays.sort(arr);
      
         //Store the frequency of each element
         Integer [] freq = new Integer[MAX];
         Arrays.fill(freq, 0 );
         int p = 0 ;
         freq
 = 1 ;
          
         //Store the frequency of elements
         for ( int i = 1 ; i <n; i++)
         {
             if (arr[i] == arr[i - 1 ])
                 ++freq
;
             else
                 ++freq[++p];
         }
      
         //Sort frequencies in descending order
         Arrays.sort(freq, Collections.reverseOrder());
          
         //To store the required answer
         int ans = 0 ;
         for ( int i = k; i <= p; i++)
             ans += freq[i];
              
         //Return the required answer
         return ans;
     }
      
     //Driver code
     public static void main (String []args)
     {
         int [] arr = { 1 , 2 , 7 , 8 , 2 , 3 , 2 , 3 };
          
         int n = arr.length;
          
         int k = 2 ;
          
         System.out.println(Min_Replace(arr, n, k));
     }
}
  
//This code is contributed by PrinciRaj1992

Python3

# Python 3 program to minimum changes required 
# in an array for k distinct elements.
MAX = 100005
  
# Function to minimum changes required 
# in an array for k distinct elements.
def Min_Replace(arr, n, k):
     arr.sort(reverse = False )
  
     # Store the frequency of each element
     freq = [ 0 for i in range ( MAX )]
      
     p = 0
     freq
 = 1
      
     # Store the frequency of elements
     for i in range ( 1 , n, 1 ):
         if (arr[i] = = arr[i - 1 ]):
             freq
 + = 1
         else :
             p + = 1
             freq
 + = 1
  
     # Sort frequencies in descending order
     freq.sort(reverse = True )
      
     # To store the required answer
     ans = 0
     for i in range (k, p + 1 , 1 ):
         ans + = freq[i]
          
     # Return the required answer
     return ans
  
# Driver code
if __name__ = = '__main__' :
     arr = [ 1 , 2 , 7 , 8 , 2 , 3 , 2 , 3 ]
      
     n = len (arr)
      
     k = 2
      
     print (Min_Replace(arr, n, k))
      
# This code is contributed by
# Surendra_Gangwar

C#

//C# program to minimum changes required 
//in an array for k distinct elements.
using System;
  
class GFG
{
     static int MAX = 100005;
      
     //Function to minimum changes required 
     //in an array for k distinct elements.
     static int Min_Replace( int [] arr, int n, int k)
     {
         Array.Sort(arr);
      
         //Store the frequency of each element
         int [] freq = new int [MAX];
          
         int p = 0;
         freq




 = 1;
          
         //Store the frequency of elements
         for ( int i = 1; i <n; i++)
         {
             if (arr[i] == arr[i - 1])
                 ++freq
;
             else
                 ++freq[++p];
         }
      
         //Sort frequencies in descending order
         Array.Sort(freq);
         Array.Reverse(freq);
          
         //To store the required answer
         int ans = 0;
         for ( int i = k; i <= p; i++)
             ans += freq[i];
              
         //Return the required answer
         return ans;
     }
      
     //Driver code
     public static void Main ()
     {
         int [] arr = { 1, 2, 7, 8, 2, 3, 2, 3 };
          
         int n = arr.Length;
          
         int k = 2;
          
         Console.WriteLine(Min_Replace(arr, n, k));
     }
}
  
//This code is contributed by ihritik

输出如下：

3

时间复杂度：O(NlogN)

---