Бүх элементүүдийг массивт тэнцүү болгох хамгийн бага ажиллагаа  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны БлэкРок Citadel Directi Flipkart Үнэндээ Yandex
Array Хаширч байна

“Бүх элементүүдийг массивт тэнцүү болгох хамгийн бага ажиллагаа” гэсэн асуудалд танд өгөгдсөн болно массив зарим нь бүхэл тоо үүн дотор. Массивыг тэнцүү болгохын тулд хийж болох хамгийн бага ажиллагааг олж мэдэх хэрэгтэй.

Жишээ нь  

Бүх элементүүдийг массивт тэнцүү болгох хамгийн бага ажиллагаа

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

Тайлбар

Тэнцүү массивыг бүрдүүлэхийн тулд 3 хасах эсвэл 3 нэмж хийх боломжтой.

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

Тайлбар

Тэнцүү массивыг бүрдүүлэхийн тулд 4 хасах эсвэл 4 нэмж хийх боломжтой.

Бүх элементүүдийг тэнцүү болгох хамгийн бага үйлдлийг олох алгоритм  

  1. Мэдүүлэх a газрын зураг.
  2. I <n байхад давталт үргэлжилнэ
    1. Массивын элемент болон элемент бүрийн давтамжийг газрын зураг дээр хадгалах.
  3. нь чансаанд “MaxCount” 0 рүү.
  4. Хэрэв давталтын шалгалтыг давтаж байвал “MaxCount” нь газрын зураг дээрх түлхүүрийн утгаас бага байна
    1. Хэрэв нөхцөл хангагдсан бол “MaxCount” түлхүүрийн утга.
  5. Буцах (n - “maxCount”).

Тайлбар

Бидэнд байгаа бүхэл тоо массив оролт байдлаар. Бидний даалгавар бол массивыг тэнцүү болгох хамгийн бага үйлдлийг олж мэдэх явдал юм. Бид дотор нь газрын зураг ашиглах гэж байна. Газрын зураг ашиглан элементүүдийг давтамжтайгаар нь хялбархан хадгалах боломжтой, учир нь давтамжууд нь үйлдлийг олоход гол үүрэг гүйцэтгэдэг.

Бид хамгийн их давтамжтай элементийг олж мэдээд массивын урт ба хамгийн их давтамжийн тооллын зөрүүг буцааж өгөх болно, учир нь энэ элемент давтагдсан массивт байгаа тул бүх элементүүдийг ижил болгохын тулд цөөн үйлдэл шаардагдана. Энэ нь тодорхой зүйлийг өөрчлөхөөс илүүтэйгээр (массивын урт - хамгийн их давтамж) энд ажилладаг.

мөн үзнэ үү
Хоёртын хайлтын мод устгах үйл ажиллагаа

Энд нэг жишээг авч үзье.

Жишээ нь

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

Эхний элементээс эхлэн бид массивыг бүхэлд нь туулж элемент бүрийн давтамжийг тоолж газрын зураг дээр хадгалдаг.

i = 0,

arr [i] = 1

countFreq = [1: 1]

би = 1

arr [i] = 5

countFreq = [1: 1,5: 1]

би = 2

arr [i] = 2

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

би = 3

arr [i] = 1

countFreq = [1: 2,5: 1,2: 1] => Энд бид "1" элементийг хоёр удаа олох тул 1-ийн давтамжийн тоог нэмэгдүүлэх болно.

би = 4

arr [i] = 3

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

би = 5

arr [i] = 2

countFreq = [1: 2,5: 1,2: 2: 3: 1] => Энд бид "2" элементийг хоёр удаа олох тул 2-ийн давтамжийн тоог нэмэгдүүлэх болно.

би = 6

arr [i] = 1

countFreq = [1: 3,5: 1,2: 2: 3: 1] => Энд бид "1" элементийг гурван удаа олох тул 1-ийн давтамжийн тоог нэмэгдүүлэх болно.

Одоо эхлүүл “MaxCount” хүртэл 0. Мөн давтамж тус бүрээс их бол шалгана уу “MaxCount”, хэрэв илүү том байвал давтамжийн утгыг хадгална уу “MaxCount”

Эцэст нь бид хамгийн их давтамжтай байх болно “MaxCount”.

Бид n- буцдаг “MaxCount” => 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

Бүх элементүүдийг массивт тэнцүү болгох Минимал ажиллагааг олох Java код

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

Нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

O (N) хаана "N" массив дахь элементүүдийн тоо юм.

мөн үзнэ үү
Хосын элементүүд өөр өөр эгнээнд байхаар өгөгдсөн нийлбэртэй хосыг ол

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" массив дахь элементүүдийн тоо юм.