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

2021年4月30日15:28:37 发表评论 629 次浏览

## 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>());

int ans = 0;
for ( int i = k; i <= p; i++)
ans += freq[i];

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());

int ans = 0 ;
for ( int i = k; i <= p; i++)
ans += freq[i];

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 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);

int ans = 0;
for ( int i = k; i <= p; i++)
ans += freq[i];

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``