การดำเนินการขั้นต่ำเพื่อทำให้องค์ประกอบทั้งหมดเท่ากันในอาร์เรย์


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน แบล็ค ป้อมปราการ Directi Flipkart จริง Yandex
แถว hashing

ปัญหา“ การดำเนินการขั้นต่ำเพื่อทำให้องค์ประกอบทั้งหมดเท่ากันในอาร์เรย์” ระบุว่าคุณได้รับไฟล์ แถว กับบางอย่าง จำนวนเต็ม ในนั้น. คุณต้องหาการดำเนินการขั้นต่ำที่สามารถทำได้เพื่อทำให้อาร์เรย์เท่ากัน

ตัวอย่าง

การดำเนินการขั้นต่ำเพื่อทำให้องค์ประกอบทั้งหมดเท่ากันในอาร์เรย์

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

คำอธิบาย

สามารถทำการลบได้ 3 ตัวหรือสามารถเพิ่ม 3 ตัวเพื่อสร้างอาร์เรย์ที่เท่ากัน

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

คำอธิบาย

สามารถทำการลบได้ 4 ตัวหรือสามารถเพิ่ม 4 ตัวเพื่อสร้างอาร์เรย์ที่เท่ากัน

อัลกอริทึมเพื่อค้นหาการดำเนินการขั้นต่ำเพื่อทำให้องค์ประกอบทั้งหมดเท่ากัน

  1. ประกาศก แผนที่.
  2. ในขณะที่ i <n การวนซ้ำยังคงดำเนินต่อไป
    1. จัดเก็บองค์ประกอบอาร์เรย์และความถี่ของแต่ละองค์ประกอบลงในแผนที่
  3. ชุด “ maxCount” เพื่อ 0
  4. การทำซ้ำในลูปตรวจสอบว่า “ maxCount” น้อยกว่าค่าของคีย์ในแผนที่
    1. หากเงื่อนไขเป็นไปตามนั้นให้ตั้งค่า “ maxCount” เป็นค่าของคีย์
  5. ผลตอบแทน (n -“ maxCount”)

คำอธิบาย

เรามี จำนวนเต็ม แถว เป็นอินพุต งานของเราคือค้นหาการดำเนินการขั้นต่ำที่สามารถทำได้เพื่อทำให้อาร์เรย์เท่ากัน เราจะใช้แผนที่ในนั้น การใช้แผนที่เราสามารถจัดเก็บองค์ประกอบด้วยความถี่ได้อย่างง่ายดายเนื่องจากความถี่มีบทบาทสำคัญในการค้นหาการดำเนินการ

เราจะหาองค์ประกอบที่มีความถี่สูงสุดและเราจะคืนค่าความแตกต่างระหว่างความยาวของอาร์เรย์และการนับความถี่สูงสุดเนื่องจากเรามีองค์ประกอบอยู่แล้วในอาร์เรย์ซึ่งทำซ้ำดังนั้นจึงใช้เวลาน้อยลงในการทำให้องค์ประกอบทั้งหมดเหมือนกัน เนื่องจากแทนที่จะเปลี่ยนเฉพาะและนั่นคือเหตุผลว่าทำไม (ความยาวของอาร์เรย์ - ความถี่สูงสุด) จึงทำงานได้

ให้เราพิจารณาตัวอย่างที่นี่:

ตัวอย่าง

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

เริ่มจากองค์ประกอบแรกสุดเราสำรวจอาร์เรย์ทั้งหมดและนับความถี่ของแต่ละองค์ประกอบและเก็บไว้ในแผนที่

ฉัน = 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

ตอนนี้เริ่มต้น “ 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” คือจำนวนองค์ประกอบในอาร์เรย์