找出包含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 = 2print (Min_Replace(arr, n, k))# This code is contributed by # Surendra_Gangwar

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

输出如下：