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

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

本文概述

给定一个大小为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)


木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: