Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

พิมพ์องค์ประกอบอาร์เรย์ที่หารอย่างน้อยหนึ่งองค์ประกอบใน C++


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

มาดูตัวอย่างเพื่อทำความเข้าใจแนวคิดกันดีกว่า

Input  : 3 12 16 21
Output : 12 21

คำอธิบาย − 3 นั้นเล็กที่สุดจึงหารด้วยจำนวนอื่นลงตัวคือ 12 หารด้วย 3 ลงตัว, 16 หารด้วย 3 ไม่ลงตัว และ 21 ลงตัวด้วย 3 ลงตัว เราจะละเลย 3 กับ 16

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

การใช้แฮช อาจเป็นทางออกที่ดีกว่า เราจะเก็บองค์ประกอบของอาร์เรย์ในแฮชแล้วค้นหาองค์ประกอบสูงสุดของอาร์เรย์ จากนั้นจนถึงองค์ประกอบสูงสุดนี้ ค้นหาทวีคูณของจำนวนที่กำหนด และหากพบหลายรายการในแฮช องค์ประกอบนั้นจะถูกหารด้วยองค์ประกอบอย่างน้อยหนึ่งรายการในอาร์เรย์ เช่นนี้ เราจะพิมพ์องค์ประกอบที่หารด้วยองค์ประกอบอย่างน้อยหนึ่งรายการในอาร์เรย์

ตัวอย่าง

ตอนนี้ ตามแนวคิดนี้ เรามาสร้างโปรแกรมกันเถอะ -

#include <bits/stdc++.h>
using namespace std;
void printDivisibleNumber(int arr[], int n){
   unordered_set<int> s;
   int maxElement = INT_MIN;
   for (int i = 0; i < n; i++) {
      s.insert(arr[i]);
      maxElement = max(maxElement, arr[i]);
   }
   unordered_set<int> res;
   for (int i = 0; i < n; i++) {
      if (arr[i] != 0) {
         for (int j = arr[i] * 2; j <= maxElement; j += arr[i]) {
            if (s.find(j) != s.end())
               res.insert(j);
            }
         }
      }
   unordered_map<int, int> mp;
   for (int i = 0; i <n; i++)
      mp[arr[i]]++;
   unordered_map<int, int>::iterator it;
   vector<int> ans;
   for (it = mp.begin(); it != mp.end(); it++) {
      if (it->second >= 2) {
         if (res.find(it->first) == res.end()) {
            int val = it->second;
            while (val--)
               ans.push_back(it->first);
         }
      }
      if (res.find(it->first) != res.end()) {
         int val = it->second;
         while (val--)
            ans.push_back(it->first);
      }
   }
   for (auto x : ans)
      cout<<x<<"\t";
}
int main(){
   int arr[] = {2, 4, 7 , 12 , 14 };
   int n = sizeof(arr) / sizeof(arr[0]);
   printDivisibleNumber(arr, n);
   return 0;
}

ผลลัพธ์

12 14 4