dsal 清空数组所需的 K 个相等元素的最小移除量

清空数组所需的 K 个相等元素的最小移除量

原文:https://www . geeksforgeeks . org/minimum-remove-k-equal-elements-需要清空数组/

给定一个由 N 个整数组成的数组arr【】，任务是计算需要移除最多 K 个等元素使数组为空的最小次数。

示例:

输入: arr[] = {1，3，1，1，3}，K = 2 输出: 3 解释: 第一步:从数组中最多移除 2 个 1s。修改后的数组是{1，3，3}。 步骤 2: 从阵列中最多移除 2 个 3s。修改后的数组是{1}。 步骤 3: 从阵列中最多移除 2 个 1s。修改后的数组是{}。 3 步后，数组变为空。因此，所需的最小步骤数为 3。

输入 : arr[] = {4，4，7，3，1，1，2，1，7，3}，K = 5 输出 : 5

天真法:最简单的方法是遍历数组统计每个数组元素的频率，然后将每个元素的频率除以 K 再加到计数中。如果数组元素的频率不能被 K 整除，则递增计数。完成上述步骤后，打印计数的值作为结果。 时间复杂度:O(N²) 辅助空间: O(1)

高效方法:上述方法可以通过哈希进行优化，存储每个数组元素的频率，然后统计所需的最小运算次数。按照以下步骤解决问题:

初始化一个变量，比如计数，它存储所需的最小步数。
初始化 Hashmap ，存储数组中每个元素的频率。
遍历数组arr【】并将每个元素的频率存储在 Hashmap 中。
遍历 Hashmap ，将每个元素的频率值除以 K ，得到变量计数。如果当前数组元素的频率不能被 K 整除，那么将计数增加 1 。
完成上述步骤后，打印计数作为使数组为空所需的最小步骤数。

下面是上述方法的实现:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;

// Function to count the minimum
// number of steps required to empty
// given array by removing at most K
// equal array elements in each operation
void minSteps(int arr[], int N, int K)
{

    // Stores the minimum number of
    // steps required to empty the array
    int count = 0;

    // Stores the occurrence
    // of each array element
    map<int, int> cntFreq;
    for (int i = 0; i < N; i++)
    {

        // Update the frequency
        cntFreq[arr[i]]++;
    }

    // Traverse the Hashmap
    for (auto i : cntFreq)
    {

        // Check if the frequency
        // is divisible by K or not
        if (i.first % K == 0)
            count += i.second / K;

        // Otherwise
        else
            count += (i.second / K) + 1;
    }

    // Print the count of
    // minimum steps required
    cout << (count);
}

// Driver Code
int main()
{

    int arr[] = { 4, 4, 7, 3, 1,
                 1, 2, 1, 7, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 5;
    minSteps(arr, N, K);
    return 0;
}

// This code is contributed by Dharanendra L V.

Java 语言(一种计算机语言，尤用于创建网站)

// Java program for the above approach

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class GFG {

    // Function to count the minimum
    // number of steps required to empty
    // given array by removing at most K
    // equal array elements in each operation
    public static void minSteps(
        int[] arr, int N, int K)
    {
        // Stores the minimum number of
        // steps required to empty the array
        int count = 0;

        // Stores the occurrence
        // of each array element
        Map<Integer, Integer> cntFreq
            = new HashMap<Integer, Integer>();

        for (int i = 0; i < N; i++) {

            // Update the frequency
            cntFreq.put(
                arr[i],
                cntFreq.getOrDefault(
                    arr[i], 0)
                    + 1);
        }

        // Traverse the Hashmap
        for (Integer i : cntFreq.keySet()) {

            // Check if the frequency
            // is divisible by K or not
            if (cntFreq.get(i) % K == 0)
                count += cntFreq.get(i)
                         / K;

            // Otherwise
            else
                count += (cntFreq.get(i)
                          / K)
                         + 1;
        }

        // Print the count of
        // minimum steps required
        System.out.print(count);
    }

    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 4, 4, 7, 3, 1,
                      1, 2, 1, 7, 3 };
        int N = arr.length;
        int K = 5;

        minSteps(arr, N, K);
    }
}

Python 3

# Python3 program for the above approach

# Function to count the minimum
# number of steps required to empty
# given array by removing at most K
# equal array elements in each operation
def minSteps(arr, N, K) :

    # Stores the minimum number of
    # steps required to empty the array
    count = 0

    # Stores the occurrence
    # of each array element
    cntFreq = {}
    for i in range(N) :

        # Update the frequency
        if arr[i] in cntFreq :
            cntFreq[arr[i]] += 1
        else :
            cntFreq[arr[i]] = 1

    # Traverse the Hashmap
    for i in cntFreq :

        # Check if the frequency
        # is divisible by K or not
        if (i % K == 0) :
            count += cntFreq[i] // K

        # Otherwise
        else :
            count += (cntFreq[i] // K) + 1

    # Print the count of
    # minimum steps required
    print(count)

arr = [ 4, 4, 7, 3, 1, 1, 2, 1, 7, 3 ]
N = len(arr)
K = 5
minSteps(arr, N, K)

# This code is contributed by divyeshabadiya07.

C

// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{

    // Function to count the minimum
    // number of steps required to empty
    // given array by removing at most K
    // equal array elements in each operation
    public static void minSteps(
        int[] arr, int N, int K)
    {
        // Stores the minimum number of
        // steps required to empty the array
        int count = 0;

        // Stores the occurrence
        // of each array element
        Dictionary<int, int> cntFreq
            = new Dictionary<int, int>();

        for (int i = 0; i < N; i++) {

            // Update the frequency
            if(cntFreq.ContainsKey(arr[i]))
                cntFreq[arr[i]] = cntFreq[arr[i]]+1;
            else

            cntFreq.Add(arr[i],1);
        }

        // Traverse the Hashmap
        foreach (int i in cntFreq.Keys) {

            // Check if the frequency
            // is divisible by K or not
            if (cntFreq[i] % K == 0)
                count += cntFreq[i]
                         / K;

            // Otherwise
            else
                count += (cntFreq[i]
                          / K)
                         + 1;
        }

        // Print the count of
        // minimum steps required
        Console.Write(count);
    }

    // Driver Code
    public static void Main(String[] args)
    {
        int []arr = { 4, 4, 7, 3, 1,
                      1, 2, 1, 7, 3 };
        int N = arr.Length;
        int K = 5;

        minSteps(arr, N, K);
    }
}

// This code is contributed by shikhasingrajput

java 描述语言

<script>
      // JavaScript program for the above approach
      // Function to count the minimum
      // number of steps required to empty
      // given array by removing at most K
      // equal array elements in each operation
      function minSteps(arr, N, K) {
        // Stores the minimum number of
        // steps required to empty the array
        var count = 0;

        // Stores the occurrence
        // of each array element
        var cntFreq = {};

        for (var i = 0; i < N; i++) {
          // Update the frequency
          if (cntFreq.hasOwnProperty(arr[i]))
              cntFreq[arr[i]] += 1;
          else
              cntFreq[arr[i]] = 1;
        }

        // Traverse the Hashmap
        for (const [key, value] of Object.entries(cntFreq)) {
          // Check if the frequency
          // is divisible by K or not
          if (key % K == 0)
              count += parseInt(cntFreq[key] / K);
          // Otherwise
          else
              count += parseInt(cntFreq[key] / K) + 1;
        }

        // Print the count of
        // minimum steps required
        document.write(count);
      }

      // Driver Code
      var arr = [4, 4, 7, 3, 1, 1, 2, 1, 7, 3];
      var N = arr.length;
      var K = 5;

      minSteps(arr, N, K);
</script>

Output:

时间复杂度:O(N) T5辅助空间:** O(N)

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://www.moonapi.com/news/36728.html

dsal 查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-11-02》

分类

最近更新

dsal 清空数组所需的 K 个相等元素的最小移除量

清空数组所需的 K 个相等元素的最小移除量

C++

Java 语言(一种计算机语言，尤用于创建网站)

Python 3

C

java 描述语言

留言

联系客服

数据知识

系统公告

开发文档

dsal查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-11-02》

dsal 清空数组所需的 K 个相等元素的最小移除量

清空数组所需的 K 个相等元素的最小移除量

C++

Java 语言(一种计算机语言，尤用于创建网站)

Python 3

C

java 描述语言

留言

联系客服

dsal 查看更多书籍