අරාවෙහි සියලු මූලද්‍රව්‍ය සමාන කිරීමට අවම ක්‍රියාකාරිත්වය


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන් කළු ගල් සිටඩෙල් ඩිරෙක්ටි ෆ්ලිප්කාර්ට් ඇත්ත වශයෙන්ම Yandex
අරා හැෂිං

“සියලු අංග අරාවෙහි සමාන කිරීමට අවම මෙහෙයුම” යන ගැටළුවෙහි දැක්වෙන්නේ ඔබට ලබා දී ඇති බවයි අරාව සමහර සමග නිඛිල එහි. අරාව සමාන කිරීමට කළ හැකි අවම මෙහෙයුම් ඔබ සොයා ගත යුතුය.

උදාහරණයක්

අරාවෙහි සියලු මූලද්‍රව්‍ය සමාන කිරීමට අවම ක්‍රියාකාරිත්වය

[ 1,3,2,4,1]
3

පැහැදිලි කිරීම

එක්කෝ අඩුකිරීම් 3 ක් කළ හැකිය, නැතහොත් සමාන අරාවක් සෑදීම සඳහා එකතු කිරීම් 3 ක් කළ හැකිය.

[5,3,2,4,1]
4

පැහැදිලි කිරීම

එක්කෝ අඩුකිරීම් 4 ක් කළ හැකිය, නැතහොත් සමාන අරාවක් සෑදීම සඳහා එකතු කිරීම් 4 ක් කළ හැකිය.

සියලුම මූලද්‍රව්‍ය සමාන කිරීමට අවම මෙහෙයුම් සොයා ගැනීමට ඇල්ගොරිතම

  1. සිතියම.
  2. මම <n අතර, ලූපය දිගටම පවතී
    1. එක් එක් මූලද්‍රව්‍යයේ අරාව මූලද්‍රව්‍යය සහ සංඛ්‍යාත සිතියම තුළ ගබඩා කරන්න.
  3. කට්ටලයක් “උපරිම ගණන” 0 දක්වා.
  4. තිබේදැයි පරීක්ෂා කරන්න “උපරිම ගණන” සිතියමක යතුරේ වටිනාකමට වඩා අඩුය
    1. තත්වය තෘප්තිමත් නම්, පසුව සකසන්න “උපරිම ගණන” යතුරේ වටිනාකමට.
  5. ආපසු (n - “maxCount”).

පැහැදිලි කිරීම

අපිට තියෙනවා නිඛිල අරාව ආදානය ලෙස. අපගේ කර්තව්‍යය වන්නේ අරාව සමාන කිරීමට කළ හැකි අවම මෙහෙයුම් සොයා ගැනීමයි. අපි එහි සිතියමක් භාවිතා කිරීමට යන්නෙමු. සිතියමක් භාවිතා කිරීමෙන් අපට මූලද්‍රව්‍ය ඒවායේ සංඛ්‍යාත සමඟ පහසුවෙන් ගබඩා කළ හැකිය, මන්ද මෙහෙයුම් සොයා ගැනීමට සංඛ්‍යාත ප්‍රධාන කාර්යභාරයක් ඉටු කරයි.

අපි උපරිම සංඛ්‍යාතයක් සහිත මූලද්‍රව්‍යය සොයා ගැනීමට යන අතර අරාවෙහි දිග සහ උපරිම සංඛ්‍යාත ගණනය අතර වෙනස අපි නැවත ලබා දෙන්නෙමු. මන්දයත් අපට දැනටමත් මූලද්‍රව්‍යයක් අරාවෙහි ඇති බැවින් එය නැවත නැවතත් පුනරාවර්තනය වේ. එය විශේෂිත දෙයක් වෙනස් කරනවාට වඩා වන අතර (අරාවේ දිග - උපරිම සංඛ්‍යාතය) එය මෙහි ක්‍රියාත්මක වන්නේ එබැවිනි.

අපි මෙහි උදාහරණයක් සලකා බලමු:

උදාහරණයක්

arr: {1, 5, 2, 1, 3, 2, 1};

පළමු මූලද්‍රව්‍යයේ සිට, අපි මුළු අරාව හරහා ගමන් කර එක් එක් මූලද්‍රව්‍යයේ සංඛ්‍යාතය ගණනය කර සිතියමට ගබඩා කරමු.

i = 0,

arr [i] = 1

countFreq = [1: 1]

i = 1

arr [i] = 5

countFreq = [1: 1,5: 1]

i = 2

arr [i] = 2

countFreq = [1: 1,5: 1,2: 1]

i = 3

arr [i] = 1

countFreq = [1: 2,5: 1,2: 1] => මෙහිදී “1” මූලද්‍රව්‍යය දෙවරක් සොයාගනු ඇත, එවිට සංඛ්‍යාත ගණන 1 වැඩි වේ.

i = 4

arr [i] = 3

countFreq=[1:2,5:1,2:1,3:1]

i = 5

arr [i] = 2

countFreq = [1: 2,5: 1,2: 2: 3: 1] => මෙහිදී “2” මූලද්‍රව්‍යය දෙවරක් සොයාගනු ඇත, එවිට සංඛ්‍යාත ගණන 2 වැඩි වේ.

i = 6

arr [i] = 1

countFreq = [1: 3,5: 1,2: 2: 3: 1] => මෙහිදී “1” මූලද්‍රව්‍යය තුන් වරක් සොයාගනු ඇත, එවිට සංඛ්‍යාත ගණන 1 වැඩි වේ.

දැන් ආරම්භ කරන්න “උපරිම ගණන” සිට 0 දක්වා. එක් එක් සංඛ්‍යාතයට වඩා වැඩි දැයි පරීක්ෂා කරන්න “උපරිම ගණන”, වඩා විශාල බව සොයා ගන්නේ නම්, එම සංඛ්‍යාතයේ අගය ගබඩා කරන්න “උපරිම ගණන”

අන්තිමේදී, අපට විශාලතම සංඛ්‍යාතය ලැබෙනු ඇත “උපරිම ගණන”.

අපි ආපසු n- “උපරිම ගණන” => 7-3 = 4, එනම් අරාව සමාන කිරීමට අපි අවම වශයෙන් මෙහෙයුම් 4 ක් කළ යුතුය.

කේතය

C ++ සියළුම මූලද්‍රව්‍යයන් අරාවෙහි සමාන කිරීමට අවම ක්‍රියාකාරිත්වය සොයා ගැනීමට

#include <bits/stdc++.h>
using namespace std;

int getMinimumOperation (int arr[], int n)
{
  unordered_map<int, int> countFreq;
  for (int i=0; i<n; i++)
    countFreq[arr[i]]++;

  int maxCount = 0;
  for (auto i : countFreq)
    if (maxCount < i.second)
      maxCount = i.second;

  return (n - maxCount);
}
int main()
{
  int arr[] = {1, 5, 2, 1, 3, 2, 1};
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << getMinimumOperation(arr, n);
  return 0;
}
4

සියලු මූලද්‍රව්‍ය අරාවෙහි සමාන කිරීමට අවම ක්‍රියාකාරිත්වය සොයා ගැනීමට ජාවා කේතය

import java.util.*;
class minimumOperations
{
    public static int getMinimumOperations(int arr[], int n)
    {
        HashMap<Integer, Integer> countFreq = new HashMap<Integer, Integer>();

        for (int i=0; i<n; i++)
        {
            if(countFreq.containsKey(arr[i]))
            {
                countFreq.put(arr[i], countFreq.get(arr[i])+1);
            }
            else
            {
                countFreq.put(arr[i], 1);
            }
        }
        int maxCount = 0;

        Set<Integer> s = countFreq.keySet();

        for (int i : s)
            if (maxCount < countFreq.get(i))
                maxCount = countFreq.get(i);


        return (n - maxCount);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 5, 2, 1, 3, 2, 1};
        int n = arr.length;
        System.out.println(getMinimumOperations(arr, n));
    }
}
4

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.