ลดขนาดอาร์เรย์ให้เหลือครึ่งหนึ่งใน C++

สมมติว่าเรามีอาร์เรย์ arr เราสามารถเลือกชุดของจำนวนเต็มและลบการเกิดของจำนวนเต็มเหล่านี้ทั้งหมดในอาร์เรย์ เราต้องหาขนาดต่ำสุดของชุดเพื่อลบจำนวนเต็มของอาร์เรย์อย่างน้อยครึ่งหนึ่ง ตัวอย่างเช่น ถ้า arr =[3,3,3,3,5,5,5,2,2,7] ผลลัพธ์จะเป็น 2 เนื่องจากถ้าเราเลือก {3,7} จะทำให้ อาร์เรย์ใหม่ [5,5,5,2,2] ซึ่งมีขนาด 5 (ซึ่งเท่ากับครึ่งหนึ่งของขนาดอาร์เรย์เก่า) ชุดที่เป็นไปได้ของขนาด 2 คือ {3,5},{3,2},{5,2} ไม่สามารถเลือกชุด {2,7} ได้ เนื่องจากจะทำให้อาร์เรย์ใหม่ [3,3,3,3,5,5,5] ซึ่งมีขนาดมากกว่าครึ่งหนึ่งของขนาดอาร์เรย์เก่า

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดแผนที่ m, n :=ขนาดของ arr, เก็บความถี่ของแต่ละองค์ประกอบที่มีอยู่ใน arr ลงในแผนที่ m

• กำหนดอาร์เรย์ที่เรียกว่า temp, sz :=n และ ret :=0

• สำหรับแต่ละคีย์-ค่าจับคู่ในหน่วย m

  • ใส่ค่าของมันลงใน temp

• จัดเรียงอาร์เรย์ชั่วคราว

• สำหรับผมอยู่ในช่วง 0 ถึงขนาดของอุณหภูมิ

  • ถ้า sz <=n / 2 ให้แยกออกจากลูป

  • เพิ่มขึ้น 1

  • ลด sz โดย temp[i]

• รีเทิร์น

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minSetSize(vector<int>& arr) {
      unordered_map <int, int> m;
      int n = arr.size();
      for(int i = 0; i < n; i++){
         m[arr[i]]++;
      }
      vector <int> temp;
      unordered_map <int, int> :: iterator it = m.begin();
      int sz = n;
      int ret = 0;
      while(it != m.end()){
         temp.push_back(it->second);
         it++;
      }
      sort(temp.rbegin(), temp.rend());
      for(int i = 0; i < temp.size(); i++){
         if(sz <= n / 2)break;
         ret++;
         sz -= temp[i];
      }
      return ret;
   }
};
main(){
   vector<int> v = {3,3,3,3,5,5,5,2,2,7};
   Solution ob;
   cout << (ob.minSetSize(v));
}

อินพุต

[3,3,3,3,5,5,5,2,2,7]

ผลลัพธ์

2