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