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


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อะโดบี ข้อเท็จจริง
แถว กัญชา

สมมติว่าเรามีข้อมูล แถว กับ "X" จำนวนองค์ประกอบ เราได้ให้โจทย์ว่าเราต้องหาการดำเนินการลบซึ่งควรเป็นจำนวนขั้นต่ำที่จำเป็นในการสร้างอาร์เรย์ที่เท่ากันเช่นอาร์เรย์จะประกอบด้วยองค์ประกอบเท่า

ตัวอย่าง

Input:

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

Output:

3

คำอธิบาย:

หลังจากลบ (4, 6, 2) 3 องค์ประกอบอาร์เรย์จะมีค่าเท่ากันคือ [1, 1, 1]

Input:

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

Output:

5

คำอธิบาย:

เราสามารถลบองค์ประกอบใดก็ได้จาก 5 องค์ประกอบเพื่อทำให้เป็นอาร์เรย์ที่เท่ากัน

ขั้นตอนวิธี

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

คำอธิบาย

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

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

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

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

  • i = 0 ใช้ arr [i] เป็น 10 และจัดเก็บ freq (10, 1)
  • i = 1 ใช้ arr [i] เป็น 3 และจัดเก็บ freq (3, 1)
  • สำหรับ i = 2 ใช้ arr [i] เป็น 4 และจัดเก็บ freq (4, 1)
  • i = 3 ใช้ arr [i] เป็น 4 เนื่องจาก 4 มีสถานที่ในแผนที่อยู่แล้วจึงเพิ่มการนับอีกหนึ่งตำแหน่งที่ตำแหน่งหลักของ 4 และจัดเก็บ Freq (4, 2)
  • i = 4 ใช้ arr [i] เป็น 2 และจัดเก็บ freq (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

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

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

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

ความซับซ้อนของเวลา

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์

ความซับซ้อนของอวกาศ

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์