ሁሉንም የዝርዝሮች አካላት ተመሳሳይ ለማድረግ አነስተኛ የመሰረዝ ክዋኔዎች


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe ፋርስት
ሰልፍ ሃሽ

የግብዓት አለን እንበል ደርድር ጋር "ኤክስ" የንጥሎች ብዛት። የስረዛዎቹን ኦፕሬሽኖች መፈለግ ያለብንን ችግር ሰጥተናል ፣ ይህም እኩል ድርድር ለማድረግ ከሚያስፈልገው ዝቅተኛ መሆን አለበት ማለትም ድርድሩ እኩል ክፍሎችን ይይዛል ፡፡

ለምሳሌ

ግቤት

[1, 1, 4, 6, 2, 1]

ውጤት

3

ማብራሪያ:

(4, 6, 2) 3 አካላትን ካስወገዱ በኋላ ድርድሩ እኩል ይሆናል ማለትም ፣ [1, 1, 1]

ግቤት

[1, 5, 4, 16, 32, 9]

ውጤት

5

ማብራሪያ:

እኩል ድርድር ለማድረግ ከ 5 ቱ አካላት ማንኛውንም ማንሳት እንችላለን ፡፡

አልጎሪዝም

  1. የሁሉም የሰልፍ አካላት ድግግሞሾችን በካርታ ውስጥ ያከማቹ።
  2. አዘጋጅ “Max_freq” ወደ INT_MIN.
  3. በካርታው ላይ ብስጭት እና የትኛው ከፍተኛው ድግግሞሽ እንዳለው ይፈትሹ።
    • አዘጋጅ “Max_freq” ወደ ከፍተኛ (max_freq ፣ እሴት) በሁሉም ድግግሞሾች መካከል ከፍተኛውን እሴት ለማግኘት ፡፡
  4. በድርድር መጠን መካከል ያለውን ልዩነት ይመልሱ “N”max_freq (n - max_freq).

ማስረጃ

ምን ያህል ዝቅተኛውን ማወቅ ያለብንበትን ችግር ሰጥተናል ስረዛ ድርድር እኩል (ተመሳሳይ አካላት) እኩል ለማድረግ ክዋኔዎች ያስፈልጋሉ። ለዚህም እኛ ለማከማቸት ካርታ እንጠቀማለን ድግግሞሽ በድርድሩ ውስጥ ከሚገኘው እያንዳንዱ ቁጥር።

ይህንን በማድረግ ከሁሉም ድግግሞሾች መካከል ትልቁን ያንን ድግግሞሽ እናገኛለን ፡፡ በካርታው ላይ በመተላለፍ ከፍተኛውን ዘዴ በመጠቀም ያንን ከፍተኛ ድግግሞሽ ማግኘት እንችላለን ፡፡ ሥራውን ከጨረሱ በኋላ ካርታ ከፍተኛውን ድግግሞሽ እንይዛለን እና የድርድርን_ዝርዝ መመለስ ያስፈልገናል - ከፍተኛው ድግግሞሽ ፣ ድርድርን እኩል ለማድረግ ሊወገዱ የሚችሉትን አነስተኛ ድግግሞሾችን ጠቅላላ ቁጥር እንመለሳለን ማለት ነው።

እስቲ አንድ ምሳሌ እንመልከት-

arr: {10, 3, 4, 4, 2, 4};

  • i = 0 ፣ arr [i] እንደ 10 ይወስዳል እና ፍሬክን (10, 1) ያከማቻል።
  • i = 1 ፣ arr [i] እንደ 3 ይወስዳል እና ፍሬክን (3, 1) ያከማቻል።
  • ለ i = 2 ፣ arr [i] ን እንደ 4 ይወስዳል እና ፍሬክን ያከማቻል (4, 1)
  • i = 3 ፣ arr [i] ን እንደ 4 ይወስዳል ፣ ምክንያቱም 4 ቀድሞውኑ በካርታ ውስጥ ቦታ አለው ፣ ምክንያቱም በ 4 ቁልፍ ቦታ ላይ አንድ ተጨማሪ ቆጠራን ይጨምራል እና ፍሬክ (4 ፣ 2)።
  • i = 4 ፣ arr [i] ን እንደ 2 ይወስዳል እና ፍሬክን (2, 1) ያከማቻል።
  • ለ i = 5 ፣ arr [i] ን እንደ 4 ይወስዳል ፣ ምክንያቱም 4 በካርታ ውስጥ ቀድሞውኑ ቦታ አለው ፣ ምክንያቱም በ 4 ቁልፍ ቦታ ላይ አንድ ተጨማሪ ቆጠራን ይጨምራል እና ፍራክ (4 ፣ 3)።

ከነዚህ ሁሉ ቁጥር '4' መካከል ከፍተኛው ድግግሞሽ ያለው 3 ነው እና ከካርታው ላይ እንደ 3 ያህል ከፍተኛውን ድግግሞሽ ካለፍን በኋላ ዋጋውን እንመልሳለን (n - max_freq) 3. ያ የእኛ ውጤት ነው ፡፡

አፈጻጸም

ሁሉንም የዝርዝሮች ንጥረ ነገሮች ተመሳሳይ ለማድረግ ለዝቅተኛ ስረዛ ክዋኔዎች C ++ ፕሮግራም

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

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

    int max_freq = INT_MIN;

    for (auto itr = freq.begin(); itr != freq.end(); itr++)
        max_freq = max(max_freq, itr->second);

    return n - max_freq;
}
int main()
{
    int arr[] = { 10, 3, 4, 4, 2, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minDelete(arr, n);
    return 0;
}
3

ሁሉንም የዝርዝሮች ንጥረ ነገሮች ተመሳሳይ ለማድረግ ለዝቅተኛ ሰርዝ ክዋኔዎች የጃቫ ፕሮግራም

import java.util.HashMap;
class minimumDeletionOperation
{
    public static int noOfMinimumDeletions(int arr[], int n)
    {
        HashMap<Integer,Integer> freq=new HashMap<Integer,Integer>();
        for(int i=0; i<arr.length; i++)
        {
            if(freq.containsKey(arr[i]))
                freq.put(arr[i], freq.get(arr[i]) + 1);
            else
                freq.put(arr[i], 1);
        }

        int max_freq=Integer.MIN_VALUE;

        for (int i:freq.keySet())
            max_freq = Math.max(max_freq, freq.get(i));

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

ሁሉንም የድርጅት አካላት ተመሳሳይ ለማድረግ ተመሳሳይ ጥቃቅን ትንንሽ ስረዛዎች ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው

የቦታ ውስብስብነት

ኦ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው